답안 #466641

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
466641	2021-08-19T21:35:01 Z	TruaShamu	동기화 (JOI13_synchronization)	Java 11	컴파일 오류	0 ms	0 KB

synchronization

#include <bits/stdc++.h>
#define FOR(i, x, y) for (int i = x; i < y; i++)
typedef long long ll;
using namespace std;

int n, m, q;
bool active[100001];
vector<int> graph[100001];
pair<int, int> edges[200001];

int info[100001], last_sync[100001];

// DFS order
int timer = 1, tin[100001], tout[100001];
// Binary lifting parents
int anc[100001][20];

void dfs(int node = 1, int parent = 0) {
    anc[node][0] = parent;
    for (int i = 1; i < 20 && anc[node][i - 1]; i++) {
        anc[node][i] = anc[anc[node][i - 1]][i - 1];
    }

    info[node] = 1;

    tin[node] = timer++;
    for (int i : graph[node]) if (i != parent) dfs(i, node);
    tout[node] = timer;
}

// Fenwick tree
int bit[100001];

void update(int pos, int val) { for (; pos <= n; pos += (pos & (-pos))) bit[pos] += val; }

int query(int pos) {
    int ans = 0;
    for (; pos; pos -= (pos & (-pos))) ans += bit[pos];
    return ans;
}

// Binary lifting
int find_ancestor(int node) {
    int lca = node;
    for (int i = 19; ~i; i--) {
        if (anc[lca][i] && query(tin[anc[lca][i]]) == query(tin[node])) lca = anc[lca][i];
    }
    return lca;
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> m >> q;
    FOR(i, 1, n) {
        cin >> edges[i].first >> edges[i].second;
        graph[edges[i].first].push_back(edges[i].second);
        graph[edges[i].second].push_back(edges[i].first);
    }
    dfs();

    FOR(i, 1, n + 1) {
        update(tin[i], -1);
        update(tout[i], 1);
    }

    while (m--) {
        int x;
        cin >> x;
        int u = edges[x].first, v = edges[x].second;
        if (anc[u][0] == v) swap(u, v);

        if (active[x]) {
            info[v] = last_sync[v] = info[find_ancestor(u)];
            update(tin[v], -1);
            update(tout[v], 1);
        } else {
            info[find_ancestor(u)] += info[v] - last_sync[v];
            update(tin[v], 1);
            update(tout[v], -1);
        }
        active[x] = !active[x];
    }

    while (q--) {
        int x;
        cin >> x;
        cout << info[find_ancestor(x)] << '\n';
    }
    return 0;
}

Compilation message

synchronization.java:1: error: illegal character: '#'
#include <bits/stdc++.h>
^
synchronization.java:1: error: class, interface, or enum expected
#include <bits/stdc++.h>
         ^
synchronization.java:2: error: illegal character: '#'
#define FOR(i, x, y) for (int i = x; i < y; i++)
^
synchronization.java:2: error: class, interface, or enum expected
#define FOR(i, x, y) for (int i = x; i < y; i++)
                                     ^
synchronization.java:2: error: class, interface, or enum expected
#define FOR(i, x, y) for (int i = x; i < y; i++)
                                            ^
synchronization.java:4: error: class, interface, or enum expected
using namespace std;
^
synchronization.java:6: error: class, interface, or enum expected
int n, m, q;
^
synchronization.java:7: error: class, interface, or enum expected
bool active[100001];
^
synchronization.java:8: error: class, interface, or enum expected
vector<int> graph[100001];
^
synchronization.java:9: error: class, interface, or enum expected
pair<int, int> edges[200001];
^
synchronization.java:11: error: class, interface, or enum expected
int info[100001], last_sync[100001];
^
synchronization.java:14: error: class, interface, or enum expected
int timer = 1, tin[100001], tout[100001];
^
synchronization.java:16: error: class, interface, or enum expected
int anc[100001][20];
^
synchronization.java:18: error: class, interface, or enum expected
void dfs(int node = 1, int parent = 0) {
^
synchronization.java:20: error: class, interface, or enum expected
    for (int i = 1; i < 20 && anc[node][i - 1]; i++) {
    ^
synchronization.java:20: error: class, interface, or enum expected
    for (int i = 1; i < 20 && anc[node][i - 1]; i++) {
                    ^
synchronization.java:20: error: class, interface, or enum expected
    for (int i = 1; i < 20 && anc[node][i - 1]; i++) {
                                                ^
synchronization.java:22: error: class, interface, or enum expected
    }
    ^
synchronization.java:26: error: class, interface, or enum expected
    tin[node] = timer++;
    ^
synchronization.java:27: error: class, interface, or enum expected
    for (int i : graph[node]) if (i != parent) dfs(i, node);
    ^
synchronization.java:28: error: class, interface, or enum expected
    tout[node] = timer;
    ^
synchronization.java:29: error: class, interface, or enum expected
}
^
synchronization.java:34: error: class, interface, or enum expected
void update(int pos, int val) { for (; pos <= n; pos += (pos & (-pos))) bit[pos] += val; }
^
synchronization.java:34: error: class, interface, or enum expected
void update(int pos, int val) { for (; pos <= n; pos += (pos & (-pos))) bit[pos] += val; }
                                       ^
synchronization.java:34: error: class, interface, or enum expected
void update(int pos, int val) { for (; pos <= n; pos += (pos & (-pos))) bit[pos] += val; }
                                                 ^
synchronization.java:34: error: class, interface, or enum expected
void update(int pos, int val) { for (; pos <= n; pos += (pos & (-pos))) bit[pos] += val; }
                                                                                         ^
synchronization.java:38: error: class, interface, or enum expected
    for (; pos; pos -= (pos & (-pos))) ans += bit[pos];
    ^
synchronization.java:38: error: class, interface, or enum expected
    for (; pos; pos -= (pos & (-pos))) ans += bit[pos];
           ^
synchronization.java:38: error: class, interface, or enum expected
    for (; pos; pos -= (pos & (-pos))) ans += bit[pos];
                ^
synchronization.java:39: error: class, interface, or enum expected
    return ans;
    ^
synchronization.java:40: error: class, interface, or enum expected
}
^
synchronization.java:45: error: class, interface, or enum expected
    for (int i = 19; ~i; i--) {
    ^
synchronization.java:45: error: class, interface, or enum expected
    for (int i = 19; ~i; i--) {
                     ^
synchronization.java:45: error: class, interface, or enum expected
    for (int i = 19; ~i; i--) {
                         ^
synchronization.java:47: error: class, interface, or enum expected
    }
    ^
synchronization.java:49: error: class, interface, or enum expected
}
^
synchronization.java:53: error: class, interface, or enum expected
    cin.tie(0);
    ^
synchronization.java:54: error: class, interface, or enum expected
    cin >> n >> m >> q;
    ^
synchronization.java:55: error: class, interface, or enum expected
    FOR(i, 1, n) {
    ^
synchronization.java:57: error: class, interface, or enum expected
        graph[edges[i].first].push_back(edges[i].second);
        ^
synchronization.java:58: error: class, interface, or enum expected
        graph[edges[i].second].push_back(edges[i].first);
        ^
synchronization.java:59: error: class, interface, or enum expected
    }
    ^
synchronization.java:62: error: class, interface, or enum expected
    FOR(i, 1, n + 1) {
    ^
synchronization.java:64: error: class, interface, or enum expected
        update(tout[i], 1);
        ^
synchronization.java:65: error: class, interface, or enum expected
    }
    ^
synchronization.java:69: error: class, interface, or enum expected
        cin >> x;
        ^
synchronization.java:70: error: class, interface, or enum expected
        int u = edges[x].first, v = edges[x].second;
        ^
synchronization.java:71: error: class, interface, or enum expected
        if (anc[u][0] == v) swap(u, v);
        ^
synchronization.java:73: error: class, interface, or enum expected
        if (active[x]) {
        ^
synchronization.java:75: error: class, interface, or enum expected
            update(tin[v], -1);
            ^
synchronization.java:76: error: class, interface, or enum expected
            update(tout[v], 1);
            ^
synchronization.java:77: error: class, interface, or enum expected
        } else {
        ^
synchronization.java:79: error: class, interface, or enum expected
            update(tin[v], 1);
            ^
synchronization.java:80: error: class, interface, or enum expected
            update(tout[v], -1);
            ^
synchronization.java:81: error: class, interface, or enum expected
        }
        ^
synchronization.java:83: error: class, interface, or enum expected
    }
    ^
synchronization.java:87: error: class, interface, or enum expected
        cin >> x;
        ^
synchronization.java:88: error: class, interface, or enum expected
        cout << info[find_ancestor(x)] << '\n';
        ^
synchronization.java:89: error: class, interface, or enum expected
    }
    ^
synchronization.java:91: error: class, interface, or enum expected
}
^
60 errors