oj.uz

Submission #13717

# Submission time Handle Problem Language Result Execution time Memory
13717 2015-03-28T14:55:04 Z gs14004 스파이 (JOI13_spy) C++14
100 / 100
 201 ms 17056 KB 
#include <cstdio>
#include <vector>
using namespace std;

int n,m;
int rj,ri;

vector<int> jg[2005], ig[2005];

int jdf[2005], idf[2005], jsz[2005], isz[2005], jrv[2005], irv[2005];
int jp, ip;

int jdfs(int x){
    jdf[x] = ++jp;
    jrv[jp] = x;
    int ret = 1;
    for (auto &i : jg[x]){
        ret += jdfs(i);
    }
    return jsz[x] = ret;
}

int idfs(int x){
    idf[x] = ++ip;
    irv[ip] = x;
    int ret = 1;
    for (auto &i : ig[x]){
        ret += idfs(i);
    }
    return isz[x] = ret;
}

int dp[2005][2005];

int main(){
    scanf("%d %d",&n,&m);
    for (int i=1; i<=n; i++) {
        int p,q;
        scanf("%d %d",&p,&q);
        if(p == 0) rj = i;
        else jg[p].push_back(i);
        if(q == 0) ri = i;
        else ig[q].push_back(i);
    }
    jdfs(rj);
    idfs(ri);
    int cnt[2005] = {};
    while (m--) {
        int lj, li;
        scanf("%d %d",&lj,&li);
        dp[idf[li]][jdf[lj]]++;
        dp[idf[li]][jdf[lj]+jsz[lj]]--;
        dp[idf[li]+isz[li]][jdf[lj]]--;
        dp[idf[li]+isz[li]][jdf[lj]+jsz[lj]]++;
    }
    for (int i=1; i<=n; i++) {
        for (int j=1; j<=n; j++) {
            dp[i][j] += dp[i][j-1];
        }
    }
    for (int i=1; i<=n; i++) {
        for (int j=1; j<=n; j++) {
            dp[j][i] += dp[j-1][i];
        }
    }
    for (int i=1; i<=n; i++) {
        printf("%d\n",dp[idf[i]][jdf[i]]);
    }
}

Subtask #1
10.0 / 10.0

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

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 17056 KB Output is correct
2 Correct 36 ms 17056 KB Output is correct
3 Correct 33 ms 17056 KB Output is correct
4 Correct 32 ms 17056 KB Output is correct
5 Correct 32 ms 17056 KB Output is correct
6 Correct 36 ms 17056 KB Output is correct
7 Correct 36 ms 17056 KB Output is correct
8 Correct 33 ms 17056 KB Output is correct

Subtask #3
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 162 ms 17056 KB Output is correct
2 Correct 161 ms 17056 KB Output is correct
3 Correct 106 ms 17056 KB Output is correct
4 Correct 169 ms 17056 KB Output is correct
5 Correct 163 ms 17056 KB Output is correct
6 Correct 148 ms 17056 KB Output is correct
7 Correct 195 ms 17056 KB Output is correct
8 Correct 201 ms 17056 KB Output is correct