| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 163204 |
2019-11-11T18:07:09 Z |
TadijaSebez |
스파이 (JOI13_spy) |
C++11 |
|
476 ms |
21376 KB |
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
const int N=2050;
int sum[N][N];
void Add(int x, int y, int f)
{
for(int i=x;i<N;i+=i&-i)
for(int j=y;j<N;j+=j&-j)
sum[i][j]+=f;
}
void Add(int x1, int x2, int y1, int y2)
{
Add(x1,y1,1);
Add(x2+1,y1,-1);
Add(x1,y2+1,-1);
Add(x2+1,y2+1,1);
}
int Get(int x, int y)
{
int ans=0;
for(int i=x;i;i-=i&-i)
for(int j=y;j;j-=j&-j)
ans+=sum[i][j];
return ans;
}
struct Tree
{
vector<int> E[N];
int lid[N],rid[N],tid,root;
Tree(){}
void AddEdge(int u, int p)
{
if(p==0) root=u;
else E[p].pb(u);
}
void DFS(int u){ lid[u]=++tid;for(int v:E[u]) DFS(v);rid[u]=tid;}
void Euler(){ DFS(root);}
} JOI,IOI;
int main()
{
int n,m,p,q;
scanf("%i %i",&n,&m);
for(int i=1;i<=n;i++)
{
scanf("%i %i",&p,&q);
JOI.AddEdge(i,p);
IOI.AddEdge(i,q);
}
JOI.Euler();
IOI.Euler();
while(m--)
{
int e,s;
scanf("%i %i",&e,&s);
Add(JOI.lid[e],JOI.rid[e],IOI.lid[s],IOI.rid[s]);
}
for(int i=1;i<=n;i++) printf("%i\n",Get(JOI.lid[i],IOI.lid[i]));
return 0;
}
Compilation message
spy.cpp: In function 'int main()':
spy.cpp:43:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%i %i",&n,&m);
~~~~~^~~~~~~~~~~~~~~
spy.cpp:46:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%i %i",&p,&q);
~~~~~^~~~~~~~~~~~~~~
spy.cpp:55:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%i %i",&e,&s);
~~~~~^~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
1912 KB |
Output is correct |
| 2 |
Correct |
3 ms |
632 KB |
Output is correct |
| 3 |
Correct |
4 ms |
1912 KB |
Output is correct |
| 4 |
Correct |
3 ms |
1656 KB |
Output is correct |
| 5 |
Correct |
4 ms |
2040 KB |
Output is correct |
| 6 |
Correct |
3 ms |
764 KB |
Output is correct |
| 7 |
Correct |
4 ms |
1912 KB |
Output is correct |
| 8 |
Correct |
4 ms |
2040 KB |
Output is correct |
| 9 |
Correct |
2 ms |
632 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
21 ms |
13176 KB |
Output is correct |
| 2 |
Correct |
9 ms |
888 KB |
Output is correct |
| 3 |
Correct |
15 ms |
12920 KB |
Output is correct |
| 4 |
Correct |
14 ms |
10872 KB |
Output is correct |
| 5 |
Correct |
16 ms |
13816 KB |
Output is correct |
| 6 |
Correct |
10 ms |
1400 KB |
Output is correct |
| 7 |
Correct |
17 ms |
13432 KB |
Output is correct |
| 8 |
Correct |
16 ms |
14328 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
360 ms |
21368 KB |
Output is correct |
| 2 |
Correct |
387 ms |
5256 KB |
Output is correct |
| 3 |
Correct |
394 ms |
20984 KB |
Output is correct |
| 4 |
Correct |
424 ms |
21376 KB |
Output is correct |
| 5 |
Correct |
426 ms |
20856 KB |
Output is correct |
| 6 |
Correct |
344 ms |
6976 KB |
Output is correct |
| 7 |
Correct |
472 ms |
21112 KB |
Output is correct |
| 8 |
Correct |
476 ms |
21128 KB |
Output is correct |
