Your code seems to also check the next element when trying to add the current element in. Try this case:

n = 3, w = 10 items = [2, 2, 9]

damn. For problem D, I thought the first condition was "if you can determine that number, print 1" for some reason. rip. How did I get 10 pretest cases?

jk plz ignore, not a runtime error, but memory limit exceeded :| (solved)

can someone help me debug for plat #3 plz. getting some weird runtime errors for the last few test cases (got cucked by regrading)

#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <vector>
#include <set>
#include <algorithm>
#include <cstring>
using namespace std;

#define MAXN 50011
#define MAXLG 18
#define INF (1<<30)

int N, M, ans[MAXN],ed[MAXN][2];
vector<int> adj[MAXN];
vector<pair<int,int> > action[MAXN];

int dpth[MAXN], p[MAXLG][MAXN];
void dfs1(int x, int par) {
    
    dpth[x] = dpth[par] + 1;
    p[0][x] = par;
    
    for (int i = 0; i < (int)adj[x].size(); i++) {
        if (adj[x][i] == par) continue;
        else dfs1(adj[x][i], x);
    }
}

multiset<int> mst[MAXN];
int dfs2(int x, int par) {
    int id = x;
    for (int i = 0; i < (int)adj[x].size(); i++) {
        if (adj[x][i] == par) continue;
        int nxt = dfs2(adj[x][i], x);
        
        if (mst[nxt].size() < mst[id].size()) {
            mst[id].insert(mst[nxt].begin(), mst[nxt].end());
        } else {
            if (mst[id].size()) mst[nxt].insert(mst[id].begin(), mst[id].end());
            id = nxt;
        }
    }
    
    for (int i = 0; i < (int)action[x].size(); i++) {
        int a = action[x][i].first, b = action[x][i].second;
        
        if (a) mst[id].insert(b);
        else if (mst[id].find(b) != mst[id].end())
            mst[id].erase(mst[id].find(b));
    }
    
    if (mst[id].size()) ans[x] = *mst[id].begin();
    else ans[x] = -1;
    return id;
}

int lca(int a, int b) {
    if (dpth[a] < dpth[b])
        swap(a,b);
    
    int diff = dpth[a] - dpth[b];
    for (int i = MAXLG-1; i >= 0; i--)
        if (diff & (1<<i)) a = p[i][a];
    
    if (a == b) return a;
    for (int i = MAXLG-1; i >= 0; i--)
        if (p[i][a] != p[i][b]) {a=p[i][a];b=p[i][b];}
    
    return p[0][a];
}

int main()
{
    if (fopen("disrupt.in", "r")) {
        freopen("disrupt.in", "r", stdin);
        freopen("disrupt.out", "w", stdout);
    } else freopen("data.in", "r", stdin);
    
    scanf("%d %d", &N, &M);
    for (int i = 1; i < N; i++) {
        int a, b;
        scanf("%d", &a);
        scanf("%d", &b);
        
        adj[a].push_back(b);
        adj[b].push_back(a);
        
        ed[i][0] = a;
        ed[i][1] = b;
    }
    
    dfs1(1,1);
    for (int i = 1; i < MAXLG; i++) {
        for (int x = 1; x <= N; x++) {
            p[i][x] = p[i-1][p[i-1][x]];
        }
    }
    
    for (int i = 1; i <= M; i++) {
        int a, b, w;
        scanf("%d", &a);
        scanf("%d", &b);
        scanf("%d", &w);
        
        int c = lca(a, b);
        if (c != a) {
            action[a].push_back(make_pair(1,w));
            action[c].push_back(make_pair(0,w));
        }
        if (c != b) {
            action[b].push_back(make_pair(1,w));
            action[c].push_back(make_pair(0,w));
        }
    }
    
    dfs2(1,1);
    for (int i = 1; i < N; i++) {
        if (p[0][ed[i][0]] == ed[i][1])
            printf("%d\n", ans[ed[i][0]]);
        else printf("%d\n", ans[ed[i][1]]);
    }
    
}

You made a pretty simple mistake. When you insert into your stack, you check to see whether it was visited right? However, as you insert it into your stack, you do not change the status of the vertex into "visited." This allows the same vertex to be inserted into the stack multiple times, causing your time complexity to boom. I was too lazy to read the problem, so I just skimmed through your code and found that small error. Your code after the change

There can be multiple stars at a point. Also, it seems that you are looping through the rectangle of each view, which might be too many operations to fit in the time limit.

I think he means div 1. E

Keep an array of indices, (we have an array a of length 2,000,000, if a[i] is marked with an index j, this means that there is an occurrence of string j at position i, if multiple strings occur at the same position, save the index of the longest string which occurs at that position). Then, we loop through all of the positions. For each position, if the position is marked and we are not currently printing a string, then we start printing the string marked by the current position. If a position is marked and we are currently printing a string, then we check to see whether the leftover string we are currently printing is longer than the string marked on the current position. If the string marked on the current position is longer than the leftover string we are currently printing, then we stop printing the leftover string and start printing the string marked on the current position. If a position is not marked and we are not in the middle of printing a string, then we just print 'a', since 'a' is the smallest letter.

I need to bookmark this :P

It seems like it's just some issues with IO methods. First, you should change scanf("%d %d", &N, &L) to scanf("%d %lld", &N, &L), seems like you forgot that L was long long. Also, you should try to use the %lld flag isntead of %I64 for USACO, or at least that's what the specifications page says, not sure whether it actually changes anything. I tried submitting your solution after altering the items above. It works.

Would this approach work?

First, reverse the string S and call it string B. Calculate all values for dp[prefix of S][prefix of B] = longest common subsequence of [prefix of S] and [prefix of B]. You can calculate this in O(N^2).

Then, you loop through all prefixes of S and prefixes of B where S and B do not intersect and find the maximum length. If there are multiple states that have the maximal answer, then choose the state where the length of the prefix of S is minimal.

If you run bellman-ford's algorithm on these states to find the shortest path, it shouldn't really matter?

I think you can alter the bitmasking so that it can visit one city more than one time. First, you can maintain an array dp[bitmasks of cities visited][current city]. Normally for bitmasks, you only try to transition to different bitmasks (i.e. you wouldn't transition from [110110][2] to [110110][3]), but in your case, you can alter the transitions a bit and allow such transitions to occur.

Oh I see! Thank you for pointing this out to me! Learn something new every day :D Thank you for helping out!

But how exactly should you increment the edges on the path by using the dfs preorder? The main solution does it by using Heavy-Light but I am not sure how to do the same thing with DFS and Segment Tree/BIT?

O.O (red coder!!)

Sorry, I don't really understand some parts of your solution. What is path root? How do we process the addition and queries by using BIT? Could I ask for some more details about your solution? Thanks :D

I don't think it is very plausible to solve Grass Planting with a Segment Tree representing the nodes of the tree. In order to a segment tree to actually be useful, you usually want to update a small number of contiguous segments, or else the time complexity will be huge. For the problem in the January contest, the preorder traversal was done to be able to update all the children of a node at once (in one contiguous segment). However in this problem, you need to update paths from one node from another, and I believe it is impossible(at least according to my current knowledge) to maintain an ordering so that you can update all the nodes on the path at once or at least efficiently. Why not Heavy-Light Decomposition? Researching it would be useful in the future.

P.S. Though I think it is unlikely that another solution exists, I would also be very interested if there is a solution other than using Heavy-Light Decomposition.

I have a question for Problem F: since k * (k-1) / 2 is increasing and n-k is decreasing, wouldn't the maximal value of the function be at the index where k * (k-1) / 2 becomes greater than n-k? If that is true, could we just binary search to find the point where k * (k-1) / 2 > n-k, and get our answer from there? Submission: 28155258 (Sorry not so familiar with ternary search so just asking)