| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 925231 |
2024-02-11T07:02:06 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});
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(i=1;i<=n;i++)
{
// printf("%lld:%lld %lld %lld\n",i,a[i],le[i],ri[i]);
}
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];
//printf("(%lld,%lld)\n",z,s);
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:85: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]
85 | for(i=0;i<uv[x].size();i++)
| ~^~~~~~~~~~~~~
regions.cpp:95: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]
95 | 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:82:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
82 | scanf("%lld %lld",&x,&y);
| ~~~~~^~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
27 ms |
113240 KB |
Output is correct |
| 2 |
Correct |
24 ms |
113240 KB |
Output is correct |
| 3 |
Correct |
28 ms |
113240 KB |
Output is correct |
| 4 |
Correct |
27 ms |
113472 KB |
Output is correct |
| 5 |
Correct |
31 ms |
113496 KB |
Output is correct |
| 6 |
Correct |
32 ms |
113496 KB |
Output is correct |
| 7 |
Correct |
38 ms |
113496 KB |
Output is correct |
| 8 |
Correct |
41 ms |
113496 KB |
Output is correct |
| 9 |
Correct |
51 ms |
114264 KB |
Output is correct |
| 10 |
Correct |
82 ms |
114488 KB |
Output is correct |
| 11 |
Correct |
105 ms |
114828 KB |
Output is correct |
| 12 |
Correct |
117 ms |
115908 KB |
Output is correct |
| 13 |
Correct |
154 ms |
116460 KB |
Output is correct |
| 14 |
Correct |
226 ms |
117208 KB |
Output is correct |
| 15 |
Correct |
252 ms |
120544 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7255 ms |
122148 KB |
Output is correct |
| 2 |
Execution timed out |
8070 ms |
122044 KB |
Time limit exceeded |
| 3 |
Execution timed out |
8084 ms |
126816 KB |
Time limit exceeded |
| 4 |
Correct |
185 ms |
116744 KB |
Output is correct |
| 5 |
Correct |
274 ms |
118588 KB |
Output is correct |
| 6 |
Correct |
921 ms |
118652 KB |
Output is correct |
| 7 |
Correct |
941 ms |
121092 KB |
Output is correct |
| 8 |
Correct |
794 ms |
128864 KB |
Output is correct |
| 9 |
Runtime error |
78 ms |
131072 KB |
Execution killed with signal 9 |
| 10 |
Runtime error |
72 ms |
131072 KB |
Execution killed with signal 9 |
| 11 |
Runtime error |
89 ms |
131072 KB |
Execution killed with signal 9 |
| 12 |
Runtime error |
98 ms |
131072 KB |
Execution killed with signal 9 |
| 13 |
Runtime error |
84 ms |
131072 KB |
Execution killed with signal 9 |
| 14 |
Runtime error |
99 ms |
131072 KB |
Execution killed with signal 9 |
| 15 |
Runtime error |
89 ms |
131072 KB |
Execution killed with signal 9 |
| 16 |
Runtime error |
81 ms |
131072 KB |
Execution killed with signal 9 |
| 17 |
Runtime error |
84 ms |
131072 KB |
Execution killed with signal 9 |
