Submission #33995

#	Time	Username	Problem	Language	Result	Execution time	Memory
33995		minhtung0404	스파이 (JOI13_spy)	C++14	10 / 100	249 ms	18008 KiB

spy

#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 (stderr)

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 / 10
• Subtask 2: 0 / 20
• Subtask 3: 0 / 70