oj.uz

답안 #171415

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
171415 2019-12-28T15:56:31 Z kuroni 동기화 (JOI13_synchronization) C++17
100 / 100
 7845 ms 19744 KB 
#include <bits/stdc++.h>
using namespace std;

const int N = 1E5 + 5, M = 2E5 + 5;

int n, m, q, d, u, f[N], g[N], ue[N], ve[N], lz[N], col[N];
int que[M];
bool chk[N], mod[N];
vector<int> adj[N], com[N];

void init() {
    for (int i = 1; i <= n; i++) {
        lz[i] = col[i] = 0;
        mod[i] = false;
        adj[i].clear(); com[i].clear();
    }
}

void DFS(int u, int p = 0) {
    col[u] = col[p];
    for (int &v : adj[u]) {
        int c = u ^ ue[v] ^ ve[v];
        if (c != p) {
            DFS(c, u);
        }
    }
}

void update(int u, int dif, int p = 0) {
    f[u] += dif; lz[u] += dif;
    for (int &v : com[u]) {
        int c = u ^ col[ue[v]] ^ col[ve[v]];
        if (!chk[v]) {
            g[v] += dif;
        } else if (c != p) {
            update(c, dif, u);
        }
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n >> m >> q;
    fill(f + 1, f + n + 1, 1);
    for (int i = 1; i < n; i++) {
        cin >> ue[i] >> ve[i];
        g[i] = 2;
    }
    for (int i = 1; i <= m; i++) {
        cin >> que[i];
    }
    d = sqrt(m / 2) + 1;
    for (int bl = 1; bl <= m; bl += d) {
        init();
        for (int i = 0; i < d && bl + i <= m; i++) {
            mod[que[bl + i]] = true;
        }
        for (int i = 1; i < n; i++) {
            if (!mod[i] && chk[i]) {
                adj[ue[i]].push_back(i);
                adj[ve[i]].push_back(i);
            }
        }
        for (int i = 1; i <= n; i++) {
            if (col[i] == 0) {
                col[0] = i;
                DFS(i);
            }
        }
        for (int i = 1; i < n; i++) {
            if (mod[i]) {
                com[col[ue[i]]].push_back(i);
                com[col[ve[i]]].push_back(i);
            }
        }
        for (int i = 0; i < d && bl + i <= m; i++) {
            int e = que[bl + i];
            if (!chk[e]) {
                int sum = (f[col[ue[e]]] + f[col[ve[e]]] + g[e]) / 2;
                update(col[ue[e]], sum - f[col[ue[e]]]);
                update(col[ve[e]], sum - f[col[ve[e]]]);
                g[e] = 0;
            }
            chk[e] = !chk[e];
        }
        for (int i = 1; i <= n; i++) {
            f[i] = f[col[i]];
        }
        for (int i = 1; i < n; i++) {
            if (!mod[i] && !chk[i]) {
                g[i] += lz[col[ue[i]]] + lz[col[ve[i]]];
            }
        }
    }
    while (q--) {
        cin >> u;
        cout << f[u] << '\n';
    }
}

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 5112 KB Output is correct
2 Correct 6 ms 5116 KB Output is correct
3 Correct 1 ms 4984 KB Output is correct
4 Correct 6 ms 5112 KB Output is correct
5 Correct 7 ms 5112 KB Output is correct
6 Correct 9 ms 5112 KB Output is correct
7 Correct 158 ms 5972 KB Output is correct
8 Correct 144 ms 6044 KB Output is correct
9 Correct 144 ms 6008 KB Output is correct
10 Correct 7486 ms 14396 KB Output is correct
11 Correct 7110 ms 14412 KB Output is correct
12 Correct 4925 ms 14636 KB Output is correct
13 Correct 3897 ms 14232 KB Output is correct
14 Correct 5747 ms 14472 KB Output is correct

Subtask #2
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2477 ms 17312 KB Output is correct
2 Correct 2414 ms 17192 KB Output is correct
3 Correct 1808 ms 18996 KB Output is correct
4 Correct 1724 ms 19008 KB Output is correct

Subtask #3
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 5112 KB Output is correct
2 Correct 11 ms 5112 KB Output is correct
3 Correct 6 ms 5112 KB Output is correct
4 Correct 6 ms 5112 KB Output is correct
5 Correct 6 ms 5112 KB Output is correct
6 Correct 9 ms 5112 KB Output is correct
7 Correct 101 ms 6008 KB Output is correct
8 Correct 4382 ms 14676 KB Output is correct
9 Correct 5082 ms 14844 KB Output is correct

Subtask #4
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5227 ms 14872 KB Output is correct
2 Correct 1702 ms 19436 KB Output is correct
3 Correct 1852 ms 19548 KB Output is correct
4 Correct 1779 ms 19744 KB Output is correct

Subtask #5
40.0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 5112 KB Output is correct
2 Correct 6 ms 5112 KB Output is correct
3 Correct 6 ms 5112 KB Output is correct
4 Correct 6 ms 5112 KB Output is correct
5 Correct 10 ms 5224 KB Output is correct
6 Correct 146 ms 6016 KB Output is correct
7 Correct 7845 ms 14552 KB Output is correct
8 Correct 5202 ms 14736 KB Output is correct
9 Correct 4123 ms 14672 KB Output is correct
10 Correct 6186 ms 15168 KB Output is correct
11 Correct 2588 ms 17792 KB Output is correct
12 Correct 2522 ms 17800 KB Output is correct
13 Correct 1765 ms 19600 KB Output is correct