oj.uz

Submission #34004

# Submission time Handle Problem Language Result Execution time Memory
34004 2017-11-06T02:09:29 Z minhtung0404 스파이 (JOI13_spy) C++14
100 / 100
 479 ms 18040 KB 
#include<bits/stdc++.h>
const int N = 2005;
using namespace std;

vector <int> adj[2][N];
int n, q, a, b, root[2];
int bit[N][N], st[N][2], en[N][2], cnt;

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

int get(int x, int y){
    int val = 0;
    for (int i = x; i > 0; i -= i&(-i)){
        for (int j = y; j > 0; j -= j&(-j)){
            val += bit[i][j];
        }
    }
    return val;
}

void dfs(int u, int p, bool num){
    st[u][num] = ++cnt;
    for (int i = 0; i < (int) adj[num][u].size(); i++){
        int v = adj[num][u][i];
        if (v == p) continue;
        dfs(v, u, num);
    }
    en[u][num] = cnt;
}

int main(){
    scanf("%d %d", &n, &q);
    for (int i = 1; i <= n; i++){
        scanf("%d%d", &a, &b);
        if (a != 0) adj[0][a].push_back(i);
        else root[0] = i;
        if (b != 0) adj[1][b].push_back(i);
        else root[1] = i;
    }
    cnt = 0; dfs(root[0], root[0], 0); cnt = 0; dfs(root[1], root[1], 1);
    while (q--){
        scanf("%d %d", &a, &b);
        update(st[a][0], st[b][1], 1); update(st[a][0], en[b][1]+1, -1); update(en[a][0]+1, st[b][1], -1); update(en[a][0]+1, en[b][1]+1, 1);
    }
    for (int i = 1; i <= n; i++){
        printf("%d\n", get(st[i][0], st[i][1]));
    }
}

Compilation message

spy.cpp: In function 'int main()':
spy.cpp:38:27: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d", &n, &q);
                           ^
spy.cpp:40:30: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d", &a, &b);
                              ^
spy.cpp:48:31: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d", &a, &b);
                               ^

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 17844 KB Output is correct
2 Correct 0 ms 17844 KB Output is correct
3 Correct 0 ms 17844 KB Output is correct
4 Correct 0 ms 17844 KB Output is correct
5 Correct 0 ms 17844 KB Output is correct
6 Correct 0 ms 17844 KB Output is correct
7 Correct 0 ms 17844 KB Output is correct
8 Correct 0 ms 17844 KB Output is correct
9 Correct 0 ms 17844 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 18036 KB Output is correct
2 Correct 3 ms 18040 KB Output is correct
3 Correct 0 ms 17844 KB Output is correct
4 Correct 0 ms 17844 KB Output is correct
5 Correct 0 ms 17976 KB Output is correct
6 Correct 3 ms 17976 KB Output is correct
7 Correct 0 ms 17976 KB Output is correct
8 Correct 9 ms 17976 KB Output is correct

Subtask #3
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 289 ms 18036 KB Output is correct
2 Correct 246 ms 18036 KB Output is correct
3 Correct 293 ms 17844 KB Output is correct
4 Correct 279 ms 17844 KB Output is correct
5 Correct 366 ms 17976 KB Output is correct
6 Correct 196 ms 17976 KB Output is correct
7 Correct 479 ms 17976 KB Output is correct
8 Correct 463 ms 17976 KB Output is correct