| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 686441 |
2023-01-25T09:39:43 Z |
vjudge1 |
Regions (IOI09_regions) |
C++14 |
|
28 ms |
26092 KB |
#include<stdio.h>
#include<vector>
#define N 200009
#define M 25000
#define B 999
using namespace std;
inline char nc()
{
static char buf[99999],*l,*r;
return l==r&&(r=(l=buf)+fread(buf,1,99999,stdin),l==r)?EOF:*l++;
}
inline void read(int&x)
{
char c=nc();for(;c<'0'||'9'<c;c=nc());
for(x=0;'0'<=c&&c<='9';x=(x<<3)+(x<<1)+(c^48),c=nc());
}
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:29:36: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
29 | if(c[a[i]].size()<=B)for(int j=0;j<c[a[i]].size();++j)
| ~^~~~~~~~~~~~~~~
regions.cpp:31:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
31 | for(int j=0;j<e[i].size();++j)sz[i]+=dfs(e[i][j]);
| ~^~~~~~~~~~~~
regions.cpp: At global scope:
regions.cpp:37:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
37 | main()
| ^~~~
regions.cpp: In function 'int main()':
regions.cpp:51:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
51 | for(int j=0;j<b[i].size();++j)upd(dfn[b[i][j]],1);
| ~^~~~~~~~~~~~
regions.cpp:52:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
52 | for(int j=0;j<c[i].size();++j)
| ~^~~~~~~~~~~~
regions.cpp:62:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
62 | for(int j=0;j<b[i].size();++j)upd(dfn[b[i][j]],-1);
| ~^~~~~~~~~~~~
regions.cpp:64:2: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
64 | for(int i=0;i<q;pr(ans[i++]),pc('\n'));pc(0);
| ^~~
regions.cpp:64:41: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
64 | for(int i=0;i<q;pr(ans[i++]),pc('\n'));pc(0);
| ^~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
8 ms |
19024 KB |
Time limit exceeded (wall clock) |
| 2 |
Execution timed out |
8 ms |
18988 KB |
Time limit exceeded (wall clock) |
| 3 |
Execution timed out |
10 ms |
19024 KB |
Time limit exceeded (wall clock) |
| 4 |
Execution timed out |
8 ms |
18996 KB |
Time limit exceeded (wall clock) |
| 5 |
Execution timed out |
9 ms |
18984 KB |
Time limit exceeded (wall clock) |
| 6 |
Execution timed out |
8 ms |
19024 KB |
Time limit exceeded (wall clock) |
| 7 |
Execution timed out |
8 ms |
19024 KB |
Time limit exceeded (wall clock) |
| 8 |
Execution timed out |
8 ms |
18984 KB |
Time limit exceeded (wall clock) |
| 9 |
Execution timed out |
8 ms |
19024 KB |
Time limit exceeded (wall clock) |
| 10 |
Execution timed out |
8 ms |
19152 KB |
Time limit exceeded (wall clock) |
| 11 |
Execution timed out |
9 ms |
19536 KB |
Time limit exceeded (wall clock) |
| 12 |
Execution timed out |
9 ms |
19536 KB |
Time limit exceeded (wall clock) |
| 13 |
Execution timed out |
10 ms |
19604 KB |
Time limit exceeded (wall clock) |
| 14 |
Execution timed out |
10 ms |
19828 KB |
Time limit exceeded (wall clock) |
| 15 |
Execution timed out |
10 ms |
20272 KB |
Time limit exceeded (wall clock) |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
13 ms |
21584 KB |
Time limit exceeded (wall clock) |
| 2 |
Execution timed out |
14 ms |
20816 KB |
Time limit exceeded (wall clock) |
| 3 |
Execution timed out |
16 ms |
22156 KB |
Time limit exceeded (wall clock) |
| 4 |
Execution timed out |
10 ms |
19884 KB |
Time limit exceeded (wall clock) |
| 5 |
Execution timed out |
13 ms |
20152 KB |
Time limit exceeded (wall clock) |
| 6 |
Execution timed out |
12 ms |
20512 KB |
Time limit exceeded (wall clock) |
| 7 |
Execution timed out |
15 ms |
20972 KB |
Time limit exceeded (wall clock) |
| 8 |
Execution timed out |
14 ms |
22396 KB |
Time limit exceeded (wall clock) |
| 9 |
Execution timed out |
18 ms |
23948 KB |
Time limit exceeded (wall clock) |
| 10 |
Execution timed out |
21 ms |
25148 KB |
Time limit exceeded (wall clock) |
| 11 |
Execution timed out |
24 ms |
23420 KB |
Time limit exceeded (wall clock) |
| 12 |
Execution timed out |
25 ms |
25640 KB |
Time limit exceeded (wall clock) |
| 13 |
Execution timed out |
23 ms |
25176 KB |
Time limit exceeded (wall clock) |
| 14 |
Execution timed out |
24 ms |
24888 KB |
Time limit exceeded (wall clock) |
| 15 |
Execution timed out |
28 ms |
26080 KB |
Time limit exceeded (wall clock) |
| 16 |
Execution timed out |
25 ms |
26056 KB |
Time limit exceeded (wall clock) |
| 17 |
Execution timed out |
24 ms |
26092 KB |
Time limit exceeded (wall clock) |
