oj.uz

Submission #131165

# Submission time Handle Problem Language Result Execution time Memory
131165 2019-07-16T17:43:26 Z zubec Synchronization (JOI13_synchronization) C++14
0 / 100
 8000 ms 14584 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;

const int N = 100100;

vector <pair<int, int> > g[N];

int tin[N], tout[N], tim, obTin[N], pr[N];

int toG[N];

int t[N*4];

int n, m, q;

void dfs(int v, int p){
    pr[v] = p;
    tin[v] = ++tim;
    obTin[tim] = v;
    for (int i = 0; i < g[v].size(); i++){
        int to = g[v][i].first, id = g[v][i].second;
        if (to == p)
            continue;
        toG[id] = to;
        dfs(to, v);
    }
    tout[v] = tim;
}

void update(int v, int l, int r, int pos, int x){
    if (l == r){
        t[v] = x;
        return;
    }
    int mid = (l+r)>>1;
    if (pos <= mid)
        update(v+v, l, mid, pos, x); else
        update(v+v+1, mid+1, r, pos, x);
    t[v] = max(t[v+v], t[v+v+1]);
}

int get(int v, int l, int r, int tl, int tr, int x){
    if (l > r || tl > r || l > tr || tl > tr || t[v] < x)
        return -1;
    if (l == r)
        return obTin[l];
    int mid = (l+r)>>1;
    int pos = -1;
    if (t[v+v+1] >= x)
        pos = get(v+v+1, mid+1, r, tl, tr, x);
    if (pos == -1 && t[v+v] >= x)
        pos = get(v+v, l, mid, tl, tr, x);
    return pos;
}

int dp[N], ob[N];

bool used[N];

int getRoot(int v){
    //cout << "kek " << v << ' ' << used[v] << endl;
    while(used[v])
        v = pr[v];
    return v;
    int cur = get(1, 1, n, 1, tin[v], tout[v]);
    if (cur != -1)
        return cur;
    return 1;
}

int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);

    cin >> n >> m >> q;
    for (int i = 1; i < n; i++){
        int u, v;
        cin >> u >> v;
        g[u].push_back({v, i});
        g[v].push_back({u, i});
    }
    dfs(1, 0);
    for (int i = 1; i <= n; i++){
        dp[i] = 1;
    }
    for (int i = 2; i <= n; i++){
        update(1, 1, n, tin[i], tout[i]);
    }
    for (int i = 1; i <= m; i++){
        int id;
        cin >> id;
        int y = toG[id];
        int x = pr[y];
        //cout << x << ' ' << y << ' ' << getRoot(x) << endl;
        if (!used[y]){
            int root = getRoot(x);
            dp[root] += dp[y] - ob[y];
            ob[y] = dp[root];
            update(1, 1, n, tin[y], 0);
        } else {
            int root = getRoot(x);
            dp[y] = dp[root];
            ob[y] = ob[root];
            update(1, 1, n, tin[y], tout[y]);
        }
        used[y] ^= 1;
        //used[id] ^= 1;
    }
    for (int i = 1; i <= q; i++){
        int x;
        cin >> x;
        cout << dp[getRoot(x)] << "\n";
    }

}

/**

5 6 3
1 2
1 3
2 4
2 5

1
2
1
4
4
3

1
4
5

*/

Compilation message

synchronization.cpp: In function 'void dfs(int, int)':
synchronization.cpp:22:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < g[v].size(); i++){
                     ~~^~~~~~~~~~~~~

Subtask #1
0 / 10.0

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

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 8101 ms 12572 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

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

Subtask #4
0 / 20.0

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

Subtask #5
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2808 KB Output is correct
2 Incorrect 12 ms 2680 KB Output isn't correct
3 Halted 0 ms 0 KB -