oj.uz

답안 #636010

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
636010 2022-08-27T14:50:56 Z Cross_Ratio 동기화 (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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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 -