oj.uz

Submission #219744

# Submission time Handle Problem Language Result Execution time Memory
219744 2020-04-06T08:37:47 Z tictaccat Synchronization (JOI13_synchronization) C++14
0 / 100
 642 ms 27756 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 4224 KB Output is correct
2 Runtime error 11 ms 8448 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 164 ms 27756 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 7 ms 4352 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 642 ms 16108 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 40.0

# Verdict Execution time Memory Grader output
1 Runtime error 11 ms 8448 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -