oj.uz

Submission #869055

# Submission time Handle Problem Language Result Execution time Memory
869055 2023-11-03T04:04:17 Z HuyQuang_re_Zero Regions (IOI09_regions) C++14
0 / 100
 320 ms 62560 KB 
#include <bits/stdc++.h>
#define ll long long
#define db long double
#define N 200005
#define II pair <ll,ll>
#define III pair <ll,II>
#define IV pair <vector <int>,vector <int> >
#define fst first
#define snd second
#define BIT(x,i) ((x>>i)&1)
#define Log(x) (31-__builtin_clz((int)x))
#define LogLL(x) (63-__builtin_clzll((ll)x))
#define pi acos(-1)
#define to_radian(x) (x*pi/180.0)
#define to_degree(x) (x*180.0/pi)
using namespace std;
int par[451][25001],child[451][25001],n,m,q,type[N],k,k1,k2,i,u,v,l[N],r[N],now,cnt[N],num[N],f[N],sz[N],root;
vector <int> pos[N],big,a[N];
vector <II> seg[N];
void dfs(int u)
{
    cnt[type[u]]++;
    l[u]=++now;
    for(int k:big) par[num[k]][type[u]]+=cnt[k];
    for(int v:a[u]) dfs(v);
    cnt[type[u]]--;


    r[u]=now;
    pos[type[u]].push_back(l[u]);
    seg[type[u]].push_back({ l[u]-1,-1 });
    seg[type[u]].push_back({ r[u],1 });
}

void DFS(int u,int k)
{
    f[u]=(type[u]==k);
    for(int v:a[u]) DFS(v,k),f[u]+=f[v];
    child[num[k]][type[u]]+=f[u];
}
int main()
{
  //  freopen("regions.inp","r",stdin);
    //freopen("regions.out","w",stdout);
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    cin>>n>>m>>q;
    cin>>type[1];
    for(i=2;i<=n;i++) cin>>u>>type[i],a[u].push_back(i),sz[type[i]]++;
    root=trunc(sqrt(n));
    for(k=1;k<=m;k++)
        if(sz[k]>root) big.push_back(k),num[k]=big.size();
    dfs(1);
    for(int k:big) DFS(1,k);
    for(k=1;k<=m;k++)
    {
        sort(pos[k].begin(),pos[k].end());
        sort(seg[k].begin(),seg[k].end());
    }

    while(q--)
    {
        cin>>k1>>k2;
        if(sz[k1]>root) cout<<par[num[k1]][k2]<<'\n';
        else if(sz[k2]>root) cout<<child[num[k2]][k1]<<'\n';
        else
        {
            int j=0,res=0;
            for(II x:seg[k1])
            {
                while(j<pos[k2].size() && pos[k2][j]<=x.fst) j++;
                res+=j*x.snd;
            }
            cout<<res<<'\n';
        }
        fflush(stdout);
    }
}

Compilation message

regions.cpp: In function 'int main()':
regions.cpp:71:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   71 |                 while(j<pos[k2].size() && pos[k2][j]<=x.fst) j++;
      |                       ~^~~~~~~~~~~~~~~

Subtask #1
0 / 15.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3 ms 21080 KB Time limit exceeded (wall clock)
2 Execution timed out 3 ms 16984 KB Time limit exceeded (wall clock)
3 Execution timed out 3 ms 16984 KB Time limit exceeded (wall clock)
4 Execution timed out 3 ms 16984 KB Time limit exceeded (wall clock)
5 Execution timed out 3 ms 17236 KB Time limit exceeded (wall clock)
6 Execution timed out 3 ms 16984 KB Time limit exceeded (wall clock)
7 Execution timed out 3 ms 16984 KB Time limit exceeded (wall clock)
8 Execution timed out 3 ms 17396 KB Time limit exceeded (wall clock)
9 Execution timed out 6 ms 17848 KB Time limit exceeded (wall clock)
10 Execution timed out 6 ms 17752 KB Time limit exceeded (wall clock)
11 Execution timed out 7 ms 18264 KB Time limit exceeded (wall clock)
12 Execution timed out 8 ms 19396 KB Time limit exceeded (wall clock)
13 Execution timed out 9 ms 19032 KB Time limit exceeded (wall clock)
14 Execution timed out 14 ms 24128 KB Time limit exceeded (wall clock)
15 Execution timed out 15 ms 28760 KB Time limit exceeded (wall clock)

Subtask #2
0 / 85.0

# Verdict Execution time Memory Grader output
1 Execution timed out 53 ms 32924 KB Time limit exceeded (wall clock)
2 Execution timed out 51 ms 29376 KB Time limit exceeded (wall clock)
3 Execution timed out 38 ms 32340 KB Time limit exceeded (wall clock)
4 Execution timed out 15 ms 19884 KB Time limit exceeded (wall clock)
5 Execution timed out 15 ms 22540 KB Time limit exceeded (wall clock)
6 Execution timed out 88 ms 36048 KB Time limit exceeded (wall clock)
7 Execution timed out 108 ms 35888 KB Time limit exceeded (wall clock)
8 Execution timed out 164 ms 54460 KB Time limit exceeded (wall clock)
9 Execution timed out 62 ms 33384 KB Time limit exceeded (wall clock)
10 Execution timed out 320 ms 62560 KB Time limit exceeded (wall clock)
11 Execution timed out 74 ms 32972 KB Time limit exceeded (wall clock)
12 Execution timed out 110 ms 37400 KB Time limit exceeded (wall clock)
13 Execution timed out 78 ms 38264 KB Time limit exceeded (wall clock)
14 Execution timed out 232 ms 42356 KB Time limit exceeded (wall clock)
15 Execution timed out 86 ms 45732 KB Time limit exceeded (wall clock)
16 Execution timed out 85 ms 55472 KB Time limit exceeded (wall clock)
17 Execution timed out 150 ms 58032 KB Time limit exceeded (wall clock)