oj.uz

Submission #869056

# Submission time Handle Problem Language Result Execution time Memory
869056 2023-11-03T04:08:10 Z HuyQuang_re_Zero Regions (IOI09_regions) C++14
100 / 100
 1564 ms 62736 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
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 21080 KB Output is correct
2 Correct 3 ms 16984 KB Output is correct
3 Correct 4 ms 16984 KB Output is correct
4 Correct 5 ms 16984 KB Output is correct
5 Correct 7 ms 16984 KB Output is correct
6 Correct 12 ms 17036 KB Output is correct
7 Correct 16 ms 16984 KB Output is correct
8 Correct 20 ms 17240 KB Output is correct
9 Correct 30 ms 18008 KB Output is correct
10 Correct 42 ms 17752 KB Output is correct
11 Correct 65 ms 18372 KB Output is correct
12 Correct 75 ms 19416 KB Output is correct
13 Correct 83 ms 19176 KB Output is correct
14 Correct 118 ms 24244 KB Output is correct
15 Correct 144 ms 28864 KB Output is correct

Subtask #2
85.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 541 ms 32656 KB Output is correct
2 Correct 590 ms 29340 KB Output is correct
3 Correct 981 ms 32288 KB Output is correct
4 Correct 148 ms 19996 KB Output is correct
5 Correct 207 ms 22744 KB Output is correct
6 Correct 379 ms 35884 KB Output is correct
7 Correct 596 ms 35692 KB Output is correct
8 Correct 664 ms 54440 KB Output is correct
9 Correct 956 ms 33412 KB Output is correct
10 Correct 1353 ms 62736 KB Output is correct
11 Correct 1564 ms 32828 KB Output is correct
12 Correct 645 ms 37404 KB Output is correct
13 Correct 868 ms 38204 KB Output is correct
14 Correct 1115 ms 42320 KB Output is correct
15 Correct 1346 ms 45600 KB Output is correct
16 Correct 1438 ms 55228 KB Output is correct
17 Correct 1399 ms 58400 KB Output is correct