Submission #219744

#	Time	Username	Problem	Language	Result	Execution time	Memory
219744		tictaccat	Synchronization (JOI13_synchronization)	C++14	0 / 100	642 ms	27756 KiB

synchronization

#include <bits/stdc++.h>

using namespace std;

const int MAX = 1e5 + 100;

int N,M,Q;
vector<vector<int>> adj(MAX);
vector<pair<int,int>> el;
vector<bool> active(MAX);
set<pair<int,int>> regions;
vector<int> r(MAX), l(MAX), rm(MAX), lm(MAX);

int main() {

    cin >> N >> M >> Q;

    for (int i = 0; i < N-1; i++) {
        int X,Y;
        cin >> X >> Y;
        X--; Y--;
        adj[X].push_back(Y);
        adj[Y].push_back(X);
        el.emplace_back(X,Y);
    }

    for (int i = 0; i < N; i++) {
        regions.insert(make_pair(i,i));
        r[i] = i;
        l[i] = i;
    }

    for (int i = 0; i < M; i++) {
        int d;
        cin >> d;
        d--;
        active[d] = !active[d];
        int u,v;
        tie(u,v) = el[d];
        //if (u > v) swap(u,v);
        if (active[d]) {
          //  cout << "adding " << u << " " << v << "\n";
            auto cur1 = --regions.lower_bound(make_pair(u+1,-1));
            auto cur2 = --regions.lower_bound(make_pair(u+2,-1));
            int a = (*cur1).first;
            int b = (*cur2).second;
           // cout << a << " " << b << "\n";
            regions.erase(cur1);
            regions.erase(cur2);
            regions.insert(make_pair(a,b));
            r[a] = max(r[a],b);
            l[b] = min(l[b],a);
        }
        if (!active[d]) {
           // cout << "removing " << u << " " << v << "\n";
            auto cur = --regions.lower_bound(make_pair(u+1,-1));
            int a,b;
            tie(a,b) = *cur;
            regions.erase(cur);
            regions.insert(make_pair(a,u));
            regions.insert(make_pair(u+1,b));
           // cout << a << " " << b << "\n";
        }
        //edge = el[d];
    }


    rm[0] = r[0];
    for (int i = 1; i < N; i++) rm[i] = max(rm[i-1],r[i]);

    lm[N-1] = l[N-1];
    for (int i = N-2; i >= 0; i--) lm[i] = min(lm[i+1],l[i]); 


    for (int q = 0; q < Q; q++) {
        int C; 
        cin >> C;
        C--;
        cout << rm[C] - lm[C] + 1 << "\n";
        //unique nodes for C
    }

    return 0;
}

• Subtask 1: 0 / 10
• Subtask 2: 0 / 20
• Subtask 3: 0 / 10
• Subtask 4: 0 / 20
• Subtask 5: 0 / 40