| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 686451 |
2023-01-25T09:52:09 Z |
vjudge1 |
Regions (IOI09_regions) |
C++14 |
|
81 ms |
27784 KB |
#include<stdio.h>
#include<vector>
#define N 200009
#define M 25000
#define B 999
using namespace std;
inline void read(int&x){scanf("%d",&x);}
inline void pc(const char&x)
{
static char buf[99999],*r=buf;
(!x||(*r++=x,r==buf+99999))&&(fwrite(buf,1,r-buf,stdout),r=buf);
}
inline void pr(const int&x){if(x>9)pr(x/10);pc(x%10+'0');}
int n,m,q,a[N],ans[N],dfn[N],sz[N],now,szsz[N],rem[N],tim[N];
vector<int>e[N],b[N],c[N],id[N];
inline int dfs(const int&i)
{
dfn[i]=++now;sz[i]=1;
++rem[a[i]];
if(c[a[i]].size()<=B)for(int j=0;j<c[a[i]].size();++j)
ans[id[a[i]][j]]+=rem[c[a[i]][j]];
for(int j=0;j<e[i].size();++j)sz[i]+=dfs(e[i][j]);
--rem[a[i]];
return sz[i];
}
inline void upd(int i,const int&x){for(;i<=n;szsz[i]+=x,i+=i&-i);}
inline int qry(int i){int ans=0;for(;i;ans+=szsz[i],i&=i-1);return ans;}
main()
{
read(n);read(m);read(q);read(a[0]);
for(int i=1,f;i<n;++i)read(f),e[--f].emplace_back(i),read(a[i]);
for(int i=0;i<n;++i)b[--a[i]].emplace_back(i);
for(int i=0,u,v;i<q;++i)
{
read(u);read(v);--u;--v;
c[v].emplace_back(u);id[v].emplace_back(i);
}
dfs(0);
for(int i=0;i<m;tim[i++]=-1);
for(int i=0;i<m;++i)if(c[i].size()>B)
{
for(int j=0;j<b[i].size();++j)upd(dfn[b[i][j]],1);
for(int j=0;j<c[i].size();++j)
{
int&wr=rem[c[i][j]];
if(tim[c[i][j]]^i)
{
wr=0;tim[c[i][j]]=i;
for(int k:b[c[i][j]])wr+=qry(dfn[k]+sz[k]-1)-qry(dfn[k]-1);
}
ans[id[i][j]]=wr;
}
for(int j=0;j<b[i].size();++j)upd(dfn[b[i][j]],-1);
}
for(int i=0;i<q;pr(ans[i++]),pc('\n'));pc(0);
}
Compilation message
regions.cpp: In function 'int dfs(const int&)':
regions.cpp:20:36: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
20 | if(c[a[i]].size()<=B)for(int j=0;j<c[a[i]].size();++j)
| ~^~~~~~~~~~~~~~~
regions.cpp:22:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
22 | for(int j=0;j<e[i].size();++j)sz[i]+=dfs(e[i][j]);
| ~^~~~~~~~~~~~
regions.cpp: At global scope:
regions.cpp:28:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
28 | main()
| ^~~~
regions.cpp: In function 'int main()':
regions.cpp:42:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
42 | for(int j=0;j<b[i].size();++j)upd(dfn[b[i][j]],1);
| ~^~~~~~~~~~~~
regions.cpp:43:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
43 | for(int j=0;j<c[i].size();++j)
| ~^~~~~~~~~~~~
regions.cpp:53:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
53 | for(int j=0;j<b[i].size();++j)upd(dfn[b[i][j]],-1);
| ~^~~~~~~~~~~~
regions.cpp:55:2: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
55 | for(int i=0;i<q;pr(ans[i++]),pc('\n'));pc(0);
| ^~~
regions.cpp:55:41: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
55 | for(int i=0;i<q;pr(ans[i++]),pc('\n'));pc(0);
| ^~
regions.cpp: In function 'void read(int&)':
regions.cpp:7:30: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
7 | inline void read(int&x){scanf("%d",&x);}
| ~~~~~^~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
8 ms |
19024 KB |
Time limit exceeded (wall clock) |
| 2 |
Execution timed out |
7 ms |
19024 KB |
Time limit exceeded (wall clock) |
| 3 |
Execution timed out |
8 ms |
19024 KB |
Time limit exceeded (wall clock) |
| 4 |
Execution timed out |
8 ms |
19024 KB |
Time limit exceeded (wall clock) |
| 5 |
Execution timed out |
8 ms |
19024 KB |
Time limit exceeded (wall clock) |
| 6 |
Execution timed out |
8 ms |
19024 KB |
Time limit exceeded (wall clock) |
| 7 |
Execution timed out |
7 ms |
19152 KB |
Time limit exceeded (wall clock) |
| 8 |
Execution timed out |
8 ms |
19152 KB |
Time limit exceeded (wall clock) |
| 9 |
Execution timed out |
13 ms |
19228 KB |
Time limit exceeded (wall clock) |
| 10 |
Execution timed out |
11 ms |
19408 KB |
Time limit exceeded (wall clock) |
| 11 |
Execution timed out |
14 ms |
19664 KB |
Time limit exceeded (wall clock) |
| 12 |
Execution timed out |
15 ms |
19892 KB |
Time limit exceeded (wall clock) |
| 13 |
Execution timed out |
15 ms |
19684 KB |
Time limit exceeded (wall clock) |
| 14 |
Execution timed out |
19 ms |
20252 KB |
Time limit exceeded (wall clock) |
| 15 |
Execution timed out |
20 ms |
20692 KB |
Time limit exceeded (wall clock) |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
25 ms |
21968 KB |
Time limit exceeded (wall clock) |
| 2 |
Execution timed out |
28 ms |
21320 KB |
Time limit exceeded (wall clock) |
| 3 |
Execution timed out |
33 ms |
22616 KB |
Time limit exceeded (wall clock) |
| 4 |
Execution timed out |
18 ms |
20128 KB |
Time limit exceeded (wall clock) |
| 5 |
Execution timed out |
18 ms |
20576 KB |
Time limit exceeded (wall clock) |
| 6 |
Execution timed out |
29 ms |
20896 KB |
Time limit exceeded (wall clock) |
| 7 |
Execution timed out |
30 ms |
21668 KB |
Time limit exceeded (wall clock) |
| 8 |
Execution timed out |
53 ms |
23236 KB |
Time limit exceeded (wall clock) |
| 9 |
Execution timed out |
51 ms |
25240 KB |
Time limit exceeded (wall clock) |
| 10 |
Execution timed out |
61 ms |
26420 KB |
Time limit exceeded (wall clock) |
| 11 |
Execution timed out |
65 ms |
25048 KB |
Time limit exceeded (wall clock) |
| 12 |
Execution timed out |
72 ms |
26828 KB |
Time limit exceeded (wall clock) |
| 13 |
Execution timed out |
81 ms |
26296 KB |
Time limit exceeded (wall clock) |
| 14 |
Execution timed out |
71 ms |
26464 KB |
Time limit exceeded (wall clock) |
| 15 |
Execution timed out |
80 ms |
27784 KB |
Time limit exceeded (wall clock) |
| 16 |
Execution timed out |
66 ms |
27552 KB |
Time limit exceeded (wall clock) |
| 17 |
Execution timed out |
65 ms |
27404 KB |
Time limit exceeded (wall clock) |
