# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
13716 |
2015-03-28T14:41:18 Z |
gs14004 |
스파이 (JOI13_spy) |
C++14 |
|
2000 ms |
1352 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 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);
for (int i=idf[li]; i<idf[li] + isz[li]; i++) {
int rev = irv[i];
if(jdf[lj] <= jdf[rev] && jdf[rev] < jdf[lj] + jsz[lj]){
cnt[rev]++;
}
}
}
for (int i=1; i<=n; i++) {
printf("%d\n",cnt[i]);
}
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
1352 KB |
Output is correct |
2 |
Correct |
0 ms |
1352 KB |
Output is correct |
3 |
Correct |
0 ms |
1352 KB |
Output is correct |
4 |
Correct |
0 ms |
1352 KB |
Output is correct |
5 |
Correct |
0 ms |
1352 KB |
Output is correct |
6 |
Correct |
0 ms |
1352 KB |
Output is correct |
7 |
Correct |
0 ms |
1352 KB |
Output is correct |
8 |
Correct |
0 ms |
1352 KB |
Output is correct |
9 |
Correct |
0 ms |
1352 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
11 ms |
1352 KB |
Output is correct |
2 |
Correct |
9 ms |
1352 KB |
Output is correct |
3 |
Correct |
0 ms |
1352 KB |
Output is correct |
4 |
Correct |
6 ms |
1352 KB |
Output is correct |
5 |
Correct |
0 ms |
1352 KB |
Output is correct |
6 |
Correct |
9 ms |
1352 KB |
Output is correct |
7 |
Correct |
4 ms |
1352 KB |
Output is correct |
8 |
Correct |
0 ms |
1352 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
2000 ms |
1352 KB |
Program timed out |
2 |
Halted |
0 ms |
0 KB |
- |