| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 925215 |
2024-02-11T04:36:14 Z |
ibm2006 |
Regions (IOI09_regions) |
C++17 |
|
8000 ms |
131072 KB |
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
ll n,i,j,k,l,r,x,y,z,w,s,t,a[1100000],b[1100000],le[1100000],ri[1100000],h[1100000],q,m,ee;
pair<ll,ll> p;
vector<pair<ll,ll>> u[1100000],vv;
vector<ll> uu[1100000],v[1100000],uv[1100000];
void dfs(ll x,ll y)
{
ll i;
le[x]=t;
t++;
for(i=0;i<h[x];i++)
{
if(v[x][i]==y)
continue;
dfs(v[x][i],x);
}
ri[x]=t;
t++;
}
int main()
{
scanf("%lld %lld %lld",&n,&m,&q);
for(i=1;i<=n;i++)
{
if(i==1)
{
scanf("%lld",&x);
a[i]=x;
uv[a[i]].push_back(i);
continue;
}
scanf("%lld %lld",&x,&y);
a[i]=y;
uv[a[i]].push_back(i);
v[x].push_back(i);
v[i].push_back(x);
h[x]++;
h[i]++;
}
t=1;
dfs(1,0);
for(i=1;i<=n;i++)
{
u[a[i]].push_back({le[i],1});
u[a[i]].push_back({ri[i]+1,-1});
uu[a[i]].push_back(le[i]);
b[a[i]]++;
}
for(i=1;i<=m;i++)
{
sort(u[i].begin(),u[i].end());
vv.clear();
s=0;
for(j=0;j<u[i].size();j++)
{
p=u[i][j];
s+=p.second;
vv.push_back({p.first,s});
}
u[i].clear();
for(j=0;j<vv.size();j++)
{
if(j+1==vv.size())
{
u[i].push_back(vv[j]);
continue;
}
if(vv[j].first!=vv[j+1].first)
u[i].push_back(vv[j]);
}
sort(uu[i].begin(),uu[i].end());
}
for(ee=0;ee<q;ee++)
{
s=0;
scanf("%lld %lld",&x,&y);
if(b[x]<b[y])
{
for(i=0;i<uv[x].size();i++)
{
z=uv[x][i];
//printf("(%lld,%lld)\n",z,s);
s+=lower_bound(uu[y].begin(),uu[y].end(),ri[z])-lower_bound(uu[y].begin(),uu[y].end(),le[z]);
}
printf("%lld\n",s);
fflush(stdout);
continue;
}
for(i=0;i<uv[y].size();i++)
{
z=uv[y][i];
w=lower_bound(u[x].begin(),u[x].end(),make_pair(le[z],ll(0)))-u[x].begin();
w--;
if(w>=0)
s+=u[x][w].second;
}
printf("%lld\n",s);
fflush(stdout);
}
}
Compilation message
regions.cpp: In function 'int main()':
regions.cpp:56:18: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
56 | for(j=0;j<u[i].size();j++)
| ~^~~~~~~~~~~~
regions.cpp:63:18: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
63 | for(j=0;j<vv.size();j++)
| ~^~~~~~~~~~
regions.cpp:65:19: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
65 | if(j+1==vv.size())
| ~~~^~~~~~~~~~~
regions.cpp:81:22: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
81 | for(i=0;i<uv[x].size();i++)
| ~^~~~~~~~~~~~~
regions.cpp:91:18: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
91 | for(i=0;i<uv[y].size();i++)
| ~^~~~~~~~~~~~~
regions.cpp:24:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
24 | scanf("%lld %lld %lld",&n,&m,&q);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
regions.cpp:29:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
29 | scanf("%lld",&x);
| ~~~~~^~~~~~~~~~~
regions.cpp:34:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
34 | scanf("%lld %lld",&x,&y);
| ~~~~~^~~~~~~~~~~~~~~~~~~
regions.cpp:78:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
78 | scanf("%lld %lld",&x,&y);
| ~~~~~^~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
52 ms |
113232 KB |
Output isn't correct |
| 2 |
Incorrect |
26 ms |
113396 KB |
Output isn't correct |
| 3 |
Incorrect |
26 ms |
113420 KB |
Output isn't correct |
| 4 |
Incorrect |
26 ms |
113404 KB |
Output isn't correct |
| 5 |
Incorrect |
28 ms |
113496 KB |
Output isn't correct |
| 6 |
Correct |
32 ms |
113496 KB |
Output is correct |
| 7 |
Incorrect |
45 ms |
113496 KB |
Output isn't correct |
| 8 |
Incorrect |
38 ms |
113748 KB |
Output isn't correct |
| 9 |
Correct |
48 ms |
114264 KB |
Output is correct |
| 10 |
Incorrect |
70 ms |
114648 KB |
Output isn't correct |
| 11 |
Incorrect |
103 ms |
114960 KB |
Output isn't correct |
| 12 |
Incorrect |
122 ms |
115968 KB |
Output isn't correct |
| 13 |
Incorrect |
138 ms |
116288 KB |
Output isn't correct |
| 14 |
Incorrect |
224 ms |
117204 KB |
Output isn't correct |
| 15 |
Correct |
238 ms |
120548 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7051 ms |
122020 KB |
Output isn't correct |
| 2 |
Execution timed out |
8086 ms |
122144 KB |
Time limit exceeded |
| 3 |
Execution timed out |
8090 ms |
126584 KB |
Time limit exceeded |
| 4 |
Incorrect |
199 ms |
117112 KB |
Output isn't correct |
| 5 |
Incorrect |
243 ms |
118636 KB |
Output isn't correct |
| 6 |
Incorrect |
940 ms |
118764 KB |
Output isn't correct |
| 7 |
Incorrect |
952 ms |
121092 KB |
Output isn't correct |
| 8 |
Incorrect |
768 ms |
129176 KB |
Output isn't correct |
| 9 |
Runtime error |
76 ms |
131072 KB |
Execution killed with signal 9 |
| 10 |
Runtime error |
73 ms |
131072 KB |
Execution killed with signal 9 |
| 11 |
Runtime error |
91 ms |
131072 KB |
Execution killed with signal 9 |
| 12 |
Runtime error |
99 ms |
131072 KB |
Execution killed with signal 9 |
| 13 |
Runtime error |
101 ms |
131072 KB |
Execution killed with signal 9 |
| 14 |
Runtime error |
97 ms |
131072 KB |
Execution killed with signal 9 |
| 15 |
Runtime error |
85 ms |
131072 KB |
Execution killed with signal 9 |
| 16 |
Runtime error |
78 ms |
131072 KB |
Execution killed with signal 9 |
| 17 |
Runtime error |
85 ms |
131072 KB |
Execution killed with signal 9 |
