oj.uz

Submission #49580

# Submission time Handle Problem Language Result Execution time Memory
49580 2018-05-31T12:51:06 Z mra2322001 Synchronization (JOI13_synchronization) C++14
100 / 100
 613 ms 68360 KB 
#include <bits/stdc++.h>
#define f0(i, n) for(int i=(0); i<n; i++)
#define f1(i, n) for(int i=(1); i<=n; i++)

using namespace std;
typedef long long ll;
const int N = 100002;

int n, m, q, dd[N], ans[N], tin[N], tout[N], t[8*N];
vector <pair <int, int> > edge; int last[N];
vector <int> a[N];

ostream& operator << (ostream &os, pair <int, int> x){
    cout << x.first << " " << x.second;
}
istream& operator >> (istream &is, pair <int, int> &x){
    cin >> x.first >> x.second;
}

int tim = 0;
void dfs(int u, int p){
    tin[u] = ++tim;
    for(auto v:a[u]) if(v != p) dfs(v, u);
    tout[u] = ++tim;
}

void up(int k, int l, int r, int i, int val){
    if(r < i || l > i) return ;
    if(l==r){
        t[k] += val;
        return ;
    }
    int mid = (l + r)/2;
    up(k*2, l, mid, i, val);
    up(k*2+1, mid + 1, r, i, val);
    int x = t[k*2], y = t[2*k+1];
    if(tout[x] > tout[y]) t[k] = x;
    else t[k] = y;
}

int get1(int k, int l, int r, int i, int val){
    if(l > i) return 0;
    if(r <= i && tout[t[k]] < tout[val]) return 0;
    if(l==r) return t[k];
    int mid = (l + r)/2;
    int y = get1(k*2 + 1, mid + 1, r, i, val);
    if(y) return y;
    else return get1(k*2, l, mid, i, val);
}

main(){
    ios_base::sync_with_stdio(0);
 
    pair <int, int> ed;
    cin >> n >> m >> q;
    f1(i, n - 1){
        cin >> ed;
        edge.push_back(ed);
        a[ed.first].push_back(ed.second);
        a[ed.second].push_back(ed.first);
    }
    dfs(1, 1);
    f1(i, n) ans[i] = 1, up(1, 1, 2*n, tin[i], i);
    while(m--){
        int d; cin >> d; --d;
        dd[d] ^= 1;
        int u = edge[d].first, v = edge[d].second;
        if(tin[u] > tin[v]) swap(u, v);
        int p = get1(1, 1, 2*n, tin[u], u);
        if(dd[d]){
            ans[p] = ans[p] + ans[v] - last[v];
            up(1, 1, 2*n, tin[v], -v);
        }
        else{
            ans[v] = ans[p];
            up(1, 1, 2*n, tin[v], v);
        }
        last[v] = ans[v];
    }
    while(q--){
        int u; cin >> u;
        cout << ans[get1(1, 1, 2*n, tin[u], u)] << endl;
    }
}

Compilation message

synchronization.cpp: In function 'std::ostream& operator<<(std::ostream&, std::pair<int, int>)':
synchronization.cpp:15:1: warning: no return statement in function returning non-void [-Wreturn-type]
 }
 ^
synchronization.cpp: In function 'std::istream& operator>>(std::istream&, std::pair<int, int>&)':
synchronization.cpp:18:1: warning: no return statement in function returning non-void [-Wreturn-type]
 }
 ^
synchronization.cpp: At global scope:
synchronization.cpp:51:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main(){
      ^

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 2680 KB Output is correct
2 Correct 4 ms 2800 KB Output is correct
3 Correct 4 ms 2800 KB Output is correct
4 Correct 5 ms 2904 KB Output is correct
5 Correct 5 ms 2956 KB Output is correct
6 Correct 6 ms 3012 KB Output is correct
7 Correct 27 ms 4056 KB Output is correct
8 Correct 27 ms 4308 KB Output is correct
9 Correct 27 ms 4516 KB Output is correct
10 Correct 385 ms 14184 KB Output is correct
11 Correct 429 ms 16332 KB Output is correct
12 Correct 267 ms 22144 KB Output is correct
13 Correct 200 ms 22144 KB Output is correct
14 Correct 217 ms 22172 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 148 ms 26176 KB Output is correct
2 Correct 137 ms 28112 KB Output is correct
3 Correct 126 ms 31572 KB Output is correct
4 Correct 114 ms 33432 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 33432 KB Output is correct
2 Correct 4 ms 33432 KB Output is correct
3 Correct 4 ms 33432 KB Output is correct
4 Correct 4 ms 33432 KB Output is correct
5 Correct 4 ms 33432 KB Output is correct
6 Correct 7 ms 33432 KB Output is correct
7 Correct 35 ms 33432 KB Output is correct
8 Correct 449 ms 36772 KB Output is correct
9 Correct 441 ms 39668 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 466 ms 42668 KB Output is correct
2 Correct 366 ms 45248 KB Output is correct
3 Correct 316 ms 47520 KB Output is correct
4 Correct 312 ms 49796 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 49796 KB Output is correct
2 Correct 4 ms 49796 KB Output is correct
3 Correct 4 ms 49796 KB Output is correct
4 Correct 4 ms 49796 KB Output is correct
5 Correct 8 ms 49796 KB Output is correct
6 Correct 42 ms 49796 KB Output is correct
7 Correct 613 ms 49796 KB Output is correct
8 Correct 508 ms 55716 KB Output is correct
9 Correct 456 ms 55716 KB Output is correct
10 Correct 489 ms 57304 KB Output is correct
11 Correct 366 ms 61948 KB Output is correct
12 Correct 322 ms 64444 KB Output is correct
13 Correct 313 ms 68360 KB Output is correct