제출 #131174

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
131174		zubec	동기화 (JOI13_synchronization)	C++14	100 / 100	290 ms	17052 KiB

synchronization

#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){
    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[id]){
            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


*/

컴파일 시 표준 에러 (stderr) 메시지

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