oj.uz

답안 #26084

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
26084 2017-06-27T13:06:13 Z yosupo 동기화 (JOI13_synchronization) C++14
50 / 100
 379 ms 22556 KB 
#include <cstdio>
#include <vector>

using namespace std;
template<class T> using V = vector<T>;

struct Node {
    using NP = Node*;
    NP l, r; int sz;
    Node(int sz) : sz(sz) {
        ma = -1;
        if (sz == 1) return;
        l = new Node(sz/2);
        r = new Node(sz-sz/2);
    }
    int ma;
    void set(int k, int x) {
        if (sz == 1) {
            ma = x;
            return;
        }
        if (k < sz/2) {
            l->set(k, x);
        } else {
            r->set(k-sz/2, x);
        }
        ma = max(l->ma, r->ma);
    }
    int sea(int b, int x) {
        if (b <= 0 || ma < x) return -1;
        if (sz == 1) return 0;
        int u = r->sea(b - sz/2, x);
        if (u != -1) return u + sz/2;
        return l->sea(b, x);
    }
};


const int MN = 100100;

V<int> g[MN];

int lc, rc;
int dps[MN], lid[MN], rid[MN], lrev[MN];
void dfs(int p, int b, int dp = 0) {
    dps[p] = p;
    lrev[lc] = p;
    lid[p] = lc++;
    for (int d: g[p]) {
        if (d == b) continue;
        dfs(d, p, dp+1);
    }
    rid[p] = rc++;
}


int vc[MN], uc[MN];

int e_x[MN], e_y[MN], e_on[MN];
int main() {
    int n, m, q;
    scanf("%d %d %d", &n, &m, &q);
    fill(vc, vc+n, 1);
    for (int i = 0; i < n-1; i++) {
        scanf("%d %d", e_x+i, e_y+i); e_x[i]--; e_y[i]--;
        g[e_x[i]].push_back(e_y[i]);
        g[e_y[i]].push_back(e_x[i]);
    }
    dfs(0, -1);
    Node* rmq = new Node(n);
    auto rt = [&](int p) {
        return lrev[rmq->sea(lid[p]+1, rid[p])];
    };
    auto ad = [&](int p) {
        rmq->set(lid[p], rid[p]);
    };
    auto er = [&](int p) {
        rmq->set(lid[p], -1);
    };
    for (int i = 0; i < n; i++) {
        ad(i);
    }
    for (int i = 0; i < m; i++) {
        int e;
        scanf("%d", &e); e--;
        int x = e_x[e], y = e_y[e];
        if (dps[x] < dps[y]) swap(x, y);
        if (!e_on[e]) {
            //inc
            vc[rt(y)] += vc[x] - uc[x];
            er(x);            
        } else {
            //dec
            vc[x] = uc[x] = vc[rt(y)];
            ad(x);
        }
        e_on[e] = 1-e_on[e];
    }

    for (int i = 0; i < q; i++) {
        int x;
        scanf("%d", &x); x--;
        printf("%d\n", vc[rt(x)]);
    }
    return 0;
}

Compilation message

synchronization.cpp: In function 'int main()':
synchronization.cpp:62:34: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d %d", &n, &m, &q);
                                  ^
synchronization.cpp:65:37: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d", e_x+i, e_y+i); e_x[i]--; e_y[i]--;
                                     ^
synchronization.cpp:85:24: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &e); e--;
                        ^
synchronization.cpp:102:24: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &x); x--;
                        ^

Subtask #1
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 7056 KB Output is correct
2 Incorrect 0 ms 7056 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 133 ms 19704 KB Output is correct
2 Correct 133 ms 19520 KB Output is correct
3 Correct 139 ms 22552 KB Output is correct
4 Correct 146 ms 22552 KB Output is correct

Subtask #3
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 7056 KB Output is correct
2 Correct 0 ms 7056 KB Output is correct
3 Correct 0 ms 7056 KB Output is correct
4 Correct 0 ms 7056 KB Output is correct
5 Correct 0 ms 7056 KB Output is correct
6 Correct 0 ms 7188 KB Output is correct
7 Correct 23 ms 8480 KB Output is correct
8 Correct 356 ms 22548 KB Output is correct
9 Correct 356 ms 22556 KB Output is correct

Subtask #4
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 379 ms 22556 KB Output is correct
2 Correct 179 ms 22512 KB Output is correct
3 Correct 159 ms 22556 KB Output is correct
4 Correct 133 ms 22552 KB Output is correct

Subtask #5
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 7056 KB Output is correct
2 Incorrect 0 ms 7056 KB Output isn't correct
3 Halted 0 ms 0 KB -