# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
964744 |
2024-04-17T13:17:33 Z |
PieArmy |
Regions (IOI09_regions) |
C++17 |
|
8000 ms |
82528 KB |
typedef long long ll;
ll pie(ll army){return (1ll<<army);}
#include <bits/stdc++.h>
#define fr first
#define sc second
#define pb push_back
#define mid ((left+right)>>1)
const ll inf=2000000000000000005;
const int sonsuz=2000000005;
using namespace std;
ll fpow(ll x,ll y,ll m=0){if(y<0){cout<<"powError";return -1;}if(m)x%=m;ll res=1;while(y>0){if(y&1)res*=x;x*=x;if(m){x%=m;res%=m;}y>>=1;}return res;}
int n,sq,R,Q;
int pre[25001][450],pre2[450][25001],say[25001],renk[200001],fazlapos[25001],bas[200001],son[200001];
vector<int>child[200001],var[25001],sirali[25001];
int cal(int a,int b){
if(say[b]==0){
return 0;
}
if(say[b]>sq){
return pre[a][fazlapos[b]];
}
if(say[a]>sq){
return pre2[fazlapos[a]][b];
}
return 0;
stack<int>sta;
int apos=0;
int ans=0;
for(int i=say[b]-1;i>=0;i--){
while(sta.size()&&bas[sta.top()]>bas[var[b][i]]){
sta.pop();
}
while(apos<say[a]&&son[sirali[a][apos]]>=bas[var[b][i]]){
if(bas[sirali[a][apos]]<=bas[var[b][i]])
sta.push(sirali[a][apos]);
apos++;
}
ans+=sta.size();
}
return ans;
}
void code(){
cin>>n>>R>>Q;
sq=sqrt(n);
cin>>renk[1];
int time=0;
say[renk[1]]++;
for(int i=2;i<=n;i++){
int par;cin>>par;
child[par].pb(i);
cin>>renk[i];
if(say[renk[i]]==sq){
fazlapos[renk[i]]=time;
time++;
}
else if(say[renk[i]]<sq){
fazlapos[renk[i]]=-1;
}
say[renk[i]]++;
}
function<int(int,int)>f=[&](int pos,int tur)->int{
int res=0;
for(int x:child[pos]){
res+=f(x,tur);
}
if(renk[pos]==tur)return res+1;
pre[renk[pos]][fazlapos[tur]]+=res;
return res;
};
function<void(int,int,int)>f2=[&](int pos,int tur,int sum)->void{
if(renk[pos]!=tur)pre2[fazlapos[tur]][renk[pos]]+=sum;
else sum++;
for(int x:child[pos]){
f2(x,tur,sum);
}
};
for(int i=1;i<=R;i++){
if(fazlapos[i]==-1)continue;
f(1,i);
f2(1,i,0);
}
time=1;
function<void(int)>turla=[&](int pos)->void{
if(say[renk[pos]]<=sq){
bas[pos]=time;
var[renk[pos]].pb(pos);
sirali[renk[pos]].pb(pos);
}
time++;
for(int x:child[pos]){
turla(x);
}
son[pos]=time-1;
};
turla(1);
for(int i=1;i<=R;i++){
if(say[i]>sq)continue;
sort(sirali[i].begin(),sirali[i].end(),[&](const int &x,const int &y){
if(son[x]==son[y]){
return bas[x]>bas[y];
}
return son[x]>son[y];
});
}
while(Q--){
int a,b;cin>>a>>b;
cout<<cal(a,b)<<endl;
}
}
int main(){
ios_base::sync_with_stdio(false);cin.tie(NULL);
bool usaco=0;if(usaco){freopen(".in","r",stdin);freopen(".out","w",stdout);}
int t=1;
if(!t)cin>>t;
while(t--){code();cout<<endl;}
return 0;
}
Compilation message
regions.cpp: In function 'int main()':
regions.cpp:116:35: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
116 | bool usaco=0;if(usaco){freopen(".in","r",stdin);freopen(".out","w",stdout);}
| ~~~~~~~^~~~~~~~~~~~~~~~~
regions.cpp:116:60: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
116 | bool usaco=0;if(usaco){freopen(".in","r",stdin);freopen(".out","w",stdout);}
| ~~~~~~~^~~~~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
12888 KB |
Output is correct |
2 |
Incorrect |
2 ms |
12888 KB |
Output isn't correct |
3 |
Incorrect |
4 ms |
12728 KB |
Output isn't correct |
4 |
Incorrect |
5 ms |
8792 KB |
Output isn't correct |
5 |
Incorrect |
5 ms |
8792 KB |
Output isn't correct |
6 |
Incorrect |
10 ms |
12888 KB |
Output isn't correct |
7 |
Incorrect |
15 ms |
8792 KB |
Output isn't correct |
8 |
Incorrect |
15 ms |
8792 KB |
Output isn't correct |
9 |
Incorrect |
23 ms |
9304 KB |
Output isn't correct |
10 |
Incorrect |
37 ms |
9104 KB |
Output isn't correct |
11 |
Incorrect |
47 ms |
9360 KB |
Output isn't correct |
12 |
Incorrect |
60 ms |
9780 KB |
Output isn't correct |
13 |
Incorrect |
81 ms |
9348 KB |
Output isn't correct |
14 |
Incorrect |
94 ms |
14140 KB |
Output isn't correct |
15 |
Incorrect |
96 ms |
18496 KB |
Output isn't correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
508 ms |
18860 KB |
Output isn't correct |
2 |
Incorrect |
533 ms |
15208 KB |
Output isn't correct |
3 |
Incorrect |
724 ms |
19524 KB |
Output isn't correct |
4 |
Incorrect |
651 ms |
20476 KB |
Output isn't correct |
5 |
Incorrect |
1980 ms |
25168 KB |
Output isn't correct |
6 |
Incorrect |
2618 ms |
31420 KB |
Output isn't correct |
7 |
Incorrect |
680 ms |
38508 KB |
Output isn't correct |
8 |
Incorrect |
821 ms |
50080 KB |
Output isn't correct |
9 |
Execution timed out |
8057 ms |
45636 KB |
Time limit exceeded |
10 |
Execution timed out |
8047 ms |
77708 KB |
Time limit exceeded |
11 |
Execution timed out |
8039 ms |
57556 KB |
Time limit exceeded |
12 |
Execution timed out |
8026 ms |
47764 KB |
Time limit exceeded |
13 |
Execution timed out |
8102 ms |
48648 KB |
Time limit exceeded |
14 |
Execution timed out |
8007 ms |
53472 KB |
Time limit exceeded |
15 |
Incorrect |
1025 ms |
71180 KB |
Output isn't correct |
16 |
Incorrect |
1222 ms |
82528 KB |
Output isn't correct |
17 |
Execution timed out |
8038 ms |
71616 KB |
Time limit exceeded |