oj.uz

Submission #636010

# Submission time Handle Problem Language Result Execution time Memory
636010 2022-08-27T14:50:56 Z Cross_Ratio Synchronization (JOI13_synchronization) C++14
10 / 100
 8000 ms 44360 KB 
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> P;
int V[200005];
int B[200005];
vector<vector<int>> C;
vector<vector<P>> adj;
struct UnionFind {
    vector<int> root;
    UnionFind(int N) {
        root.resize(N);
        fill(root.begin(),root.end(),-1);
    }
    int Find(int n) {
        if(root[n]<0) return n;
        int r = Find(root[n]);
        root[n] = r;
        return r;
    }
    void Merge(int x, int y) {
        x = Find(x), y = Find(y);
        if(x==y) return;
        if(root[x]>root[y]) swap(x, y);
        root[x] += root[y];
        root[y] = x;
    }
};
int Bu = 300;
int par[200005];
array<int, 2> Edge[200005];
bool type[200005]; // Edge type
bool change[200005];
int D[200005];
int id[200005];
map<int,int> son[200005];
void dfs(int c, int p) {
    par[c] = p;
    int dat = 0;
    for(P n2 : adj[c]) {
        int n = n2.first;
        if(n==p) continue;
        dfs(n, c);
        son[c][n] = dat;
        dat++;
    }
    C[c].resize(dat);
}
int go_par[200005];
vector<vector<P>> adj2;
void dfs2(int c, int p, int pl) {
    B[c] = pl;
    for(P k2 : adj[c]) {
        if(k2.first!=p&&type[k2.second]) {
            dfs2(k2.first, c, pl);
        }
    }
}
signed main() {
    cin.sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int N, M, Q;
    cin >> N >> M >> Q;
    adj.resize(N);
    C.resize(N);
    int i, j;
    for(i=0;i<N-1;i++) {
        int a, b;
        cin >> a >> b;
        adj[a-1].push_back(P(b-1,i));
        adj[b-1].push_back(P(a-1,i));
        Edge[i] = {a-1, b-1};
    }
    for(i=0;i<N;i++) V[i] = B[i] = 1;
    for(i=0;i<M;i++) {
        cin >> D[i];
        D[i]--;
    }
    dfs(0, -1);
    for(i=0;i<N;i++) go_par[i] = -1;
    for(i=0;i<N-1;i++) {
        if(Edge[i][0]!=par[Edge[i][1]]) {
            int x = Edge[i][0];
            int y = Edge[i][1];
            Edge[i] = {y, x};
        }
        go_par[Edge[i][1]] = i;
    }
    int pt = 0;
    vector<bool> con(N);
    for(j=0;j<N;j++) {
        if(go_par[j]!=-1&&type[go_par[j]]) {
            con[j] = true;
        }
    }
    for(j=0;j<M;j++) {
        if(type[D[j]]) {
            type[D[j]] = false;
            con[Edge[D[j]][1]] = false;
        }
        else {
            int p = Edge[D[j]][0];
            int v = Edge[D[j]][1];
            int ch = son[p][v];
            int pl = V[v] - C[p][ch];
            int top = p;
            int dat = v;
            while(top != -1) {
                V[top] += pl;
                C[top][son[top][dat]] = V[dat];
                if(!con[top]) break;
                dat = top;
                top = par[top];
            }
            con[v] = true;
            type[D[j]] = true;
            dfs2(p, -1, B[p] + pl);
        }
    }
    while(Q--) {
        int k;
        cin >> k;
        cout << B[k-1] << '\n';
    }
}

Compilation message

synchronization.cpp: In function 'int main()':
synchronization.cpp:89:9: warning: unused variable 'pt' [-Wunused-variable]
   89 |     int pt = 0;
      |         ^~

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9684 KB Output is correct
2 Correct 5 ms 9632 KB Output is correct
3 Correct 5 ms 9684 KB Output is correct
4 Correct 5 ms 9684 KB Output is correct
5 Correct 5 ms 9684 KB Output is correct
6 Correct 6 ms 9876 KB Output is correct
7 Correct 20 ms 11760 KB Output is correct
8 Correct 17 ms 11732 KB Output is correct
9 Correct 17 ms 11732 KB Output is correct
10 Correct 243 ms 30012 KB Output is correct
11 Correct 234 ms 30012 KB Output is correct
12 Correct 125 ms 43472 KB Output is correct
13 Execution timed out 8039 ms 28580 KB Time limit exceeded
14 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

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

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9684 KB Output is correct
2 Correct 5 ms 9684 KB Output is correct
3 Correct 5 ms 9684 KB Output is correct
4 Correct 5 ms 9740 KB Output is correct
5 Correct 5 ms 9684 KB Output is correct
6 Correct 6 ms 10004 KB Output is correct
7 Correct 17 ms 13140 KB Output is correct
8 Correct 145 ms 44360 KB Output is correct
9 Correct 139 ms 44292 KB Output is correct

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 151 ms 41428 KB Output is correct
2 Execution timed out 8048 ms 42396 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #5
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9684 KB Output is correct
2 Correct 7 ms 9740 KB Output is correct
3 Correct 5 ms 9684 KB Output is correct
4 Correct 5 ms 9740 KB Output is correct
5 Correct 6 ms 9940 KB Output is correct
6 Correct 21 ms 11744 KB Output is correct
7 Correct 271 ms 30860 KB Output is correct
8 Correct 137 ms 44236 KB Output is correct
9 Execution timed out 8069 ms 28972 KB Time limit exceeded
10 Halted 0 ms 0 KB -