oj.uz

Submission #220295

# Submission time Handle Problem Language Result Execution time Memory
220295 2020-04-07T14:55:47 Z tictaccat Synchronization (JOI13_synchronization) C++14
30 / 100
 944 ms 89964 KB 
#include <bits/stdc++.h>

using namespace std;

const int MAX = 1e5 + 100;

int sz = 1<<20;
vector<int> lzR(2*sz, -1), lzL(2*sz, 1e9), valsR(2*sz, -1), valsL(2*sz, 1e9);

void upd(int i, int l, int r, int x, int y, int valR, int valL) {
    if (y < x) return;
    valR = max(valR, lzR[i]);
    valL = min(valL, lzL[i]);
    if (x == l && y == r) {
        lzR[i] = max(lzR[i], valR);
        lzL[i] = min(lzL[i], valL);
        valsR[i] = max(valsR[i], valR);
        valsL[i] = min(valsL[i], valL);
        return;
    }
    int mid = (l+r)/2;
    upd(2*i, l, mid, x, min(y,mid), valR, valL);
    upd(2*i+1, mid+1, r, max(x,mid+1), y, valR, valL);
    valsR[i] = max(valsR[2*i], valsR[2*i+1]);
    valsL[i] = min(valsL[2*i], valsL[2*i+1]);
}

pair<int,int> query(int i, int l, int r, int x, int y) {
    if (y < x) return make_pair(-1,1e9);
    if (x == l && y == r) return make_pair(valsR[i],valsL[i]);
    int mid = (l+r)/2;
    auto q1 = query(2*i,l,mid, x, min(y,mid));
    auto q2 = query(2*i+1,mid+1,r, max(x,mid+1), y);
    int retR = max(q1.first, max(q2.first, lzR[i]));
    int retL = min(q1.second, min(q2.second, lzL[i]));
    return make_pair(retR, retL);
}

pair<int,int> query(int x, int y) {return query(1,0,sz-1,x,y);}
void upd(int x, int y, int valR, int valL) {upd(1,0,sz-1,x,y,valR,valL);}

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

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));
        upd(i,i,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));
            upd(a,b,query(b,b).first,query(a,a).second);
        }
        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];
    }


    for (int q = 0; q < Q; q++) {
        int C; 
        cin >> C;
        C--;
        //cout << C << "\n";
        cout << query(C,C).first - query(C,C).second + 1 << "\n";
        //unique nodes for C
    }

    return 0;
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 35584 KB Output is correct
2 Runtime error 61 ms 71800 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 310 ms 89964 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 35584 KB Output is correct
2 Correct 28 ms 35708 KB Output is correct
3 Correct 31 ms 35576 KB Output is correct
4 Correct 23 ms 35584 KB Output is correct
5 Correct 23 ms 35584 KB Output is correct
6 Correct 31 ms 35584 KB Output is correct
7 Correct 105 ms 36600 KB Output is correct
8 Correct 942 ms 47340 KB Output is correct
9 Correct 909 ms 47272 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 944 ms 46000 KB Output is correct
2 Correct 649 ms 46956 KB Output is correct
3 Correct 703 ms 47016 KB Output is correct
4 Correct 682 ms 47084 KB Output is correct

Subtask #5
0 / 40.0

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