oj.uz

Submission #131172

# Submission time Handle Problem Language Result Execution time Memory
131172 2019-07-16T17:52:03 Z zubec Synchronization (JOI13_synchronization) C++14
40 / 100
 8000 ms 17516 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) << ' ' << dp[y] << ' ' << ob[y] << 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] = dp[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

2 5 1
1 2
1
1
1
1
1
1


*/

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
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2680 KB Output is correct
2 Correct 4 ms 2684 KB Output is correct
3 Correct 4 ms 2808 KB Output is correct
4 Correct 4 ms 2680 KB Output is correct
5 Correct 4 ms 2808 KB Output is correct
6 Correct 5 ms 2808 KB Output is correct
7 Correct 16 ms 3704 KB Output is correct
8 Correct 17 ms 3704 KB Output is correct
9 Correct 16 ms 3704 KB Output is correct
10 Correct 175 ms 12760 KB Output is correct
11 Correct 185 ms 12676 KB Output is correct
12 Correct 145 ms 16632 KB Output is correct
13 Correct 132 ms 12392 KB Output is correct
14 Correct 130 ms 11708 KB Output is correct

Subtask #2
0 / 20.0

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

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2680 KB Output is correct
2 Correct 4 ms 2680 KB Output is correct
3 Correct 4 ms 2812 KB Output is correct
4 Correct 4 ms 2808 KB Output is correct
5 Correct 4 ms 2680 KB Output is correct
6 Correct 5 ms 2936 KB Output is correct
7 Correct 17 ms 4216 KB Output is correct
8 Correct 163 ms 17516 KB Output is correct
9 Correct 162 ms 17516 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 164 ms 14556 KB Output is correct
2 Correct 6868 ms 17120 KB Output is correct
3 Correct 7027 ms 17112 KB Output is correct
4 Correct 7014 ms 16908 KB Output is correct

Subtask #5
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2680 KB Output is correct
2 Correct 4 ms 2808 KB Output is correct
3 Correct 4 ms 2680 KB Output is correct
4 Correct 5 ms 2680 KB Output is correct
5 Correct 5 ms 2808 KB Output is correct
6 Correct 18 ms 3832 KB Output is correct
7 Correct 194 ms 13504 KB Output is correct
8 Correct 159 ms 17436 KB Output is correct
9 Correct 150 ms 13544 KB Output is correct
10 Correct 170 ms 12888 KB Output is correct
11 Execution timed out 8054 ms 14136 KB Time limit exceeded
12 Halted 0 ms 0 KB -