Submission #49580

#	Time	Username	Problem	Language	Result	Execution time	Memory
49580		mra2322001	Synchronization (JOI13_synchronization)	C++14	100 / 100	613 ms	68360 KiB

synchronization

#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 (stderr)

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 / 10
• Subtask 2: 20 / 20
• Subtask 3: 10 / 10
• Subtask 4: 20 / 20
• Subtask 5: 40 / 40