oj.uz

Submission #33995

# Submission time Handle Problem Language Result Execution time Memory
33995 2017-11-06T02:01:23 Z minhtung0404 스파이 (JOI13_spy) C++14
10 / 100
 249 ms 18008 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[2][N], 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 < 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 'void dfs(int, int, bool)':
spy.cpp:29:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < adj[num][u].size(); i++){
                       ^
spy.cpp: In function 'int main()':
spy.cpp:38:26: 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:30: 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
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 18004 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 70.0

# Verdict Execution time Memory Grader output
1 Incorrect 249 ms 18008 KB Output isn't correct
2 Halted 0 ms 0 KB -