oj.uz

Submission #958012

# Submission time Handle Problem Language Result Execution time Memory
958012 2024-04-04T16:24:58 Z tosivanmak Regions (IOI09_regions) C++17
95 / 100
 8000 ms 98380 KB 
#include<bits/stdc++.h>
using namespace std;
#define ll int
#define pb push_back
const ll B=1400;
vector<ll>adj[220005];
bool vis[220005];
ll siz[220005],dep[220005];
ll rem[220005];
bool used[220005];
vector<ll>compo[220005];
int fa[220005];
ll inside[220005];
ll tin[220005],tout[220005];
ll disc[250005];
vector<ll>reg[25005];
vector<ll>blk[145];
ll timer=1;
map<pair<ll,ll>,bool>hv;
map<pair<ll,ll>,ll>ans;
ll ass;
void dfs(ll s){
    vis[s]=1;
    siz[s]=1;
    tin[s]=timer++;
    for(auto& u: adj[s]){
      if(!vis[u]){
          dep[u]=dep[s]+1;
          fa[u]=s;
          dfs(u);
          siz[s]+=siz[u];
      }
    }
    tout[s]=timer;
}
void create(ll s){
    if(used[s])return;
    used[s]=1;
    inside[s]=ass;
    for(auto& u: adj[s]){
        if(!used[u]){
            create(u);
        }
    }
}
struct node{
    ll id,dep;
    bool operator<(const node& n)const{
        return dep<n.dep;
    }
    node(ll _id, ll _dep){
        id=_id,dep=_dep;
    }
};
ll cnt[145][25005];
ll tot[145][25005];
ll store[145];

ll home[200005];
ll anc(ll u, ll v){
    return ((tin[u]<=tin[v])&&(tout[u]>=tout[v])&&(u!=v));
}
vector<node>revdep;
int main(){
    ll n,r,q;
    cin>>n>>r>>q;

    for(int i=1;i<=n;i++){
        if(i==1){
            cin>>home[i];
            reg[home[i]].pb(i);
        }
        else{
            ll con;
            cin>>con;
            adj[con].push_back(i);
            cin>>home[i];
            reg[home[i]].pb(i);
        }
    }
    ass=n+1;
    dfs(1);
    for(int i=1;i<=n;i++){
        inside[i]=i;
        revdep.pb(node(i,dep[i]));
    }
    sort(revdep.rbegin(),revdep.rend());
    for(int i=0;i<revdep.size();i++){
        ll s=revdep[i].id;
        rem[s]=1;
        for(auto& u: adj[s]){
            rem[s]+=rem[u];
        }
        ll sz=0;
        vector<ll>cur;
        for(auto& u: adj[s]){
            sz+=rem[u];
            cur.pb(u);
            if(sz>=B){
                rem[s]-=sz;
                sz=0;
                for(auto& k: cur){
                    create(k);
                }
                fa[ass]=s;
                ass++;
                cur.clear();
            }
        }
        if(s==1){
            for(auto& k: cur){
                    create(k);
                }
                fa[ass]=s;
                ass++;
                cur.clear();
        }
    }
    vector<ll>lis;
    for(int i=1;i<=n;i++){
        lis.pb(inside[i]);
    }
    for(int i=1;i<=n;i++){
        compo[inside[i]].pb(i);
    }
    sort(lis.begin(),lis.end());
    lis.erase(unique(lis.begin(),lis.end()),lis.end());
    for(int i=0;i<lis.size();i++){
        disc[lis[i]]=i+1;
    }
    
    for(int i: lis){
        for(auto& u: compo[i]){
            cnt[disc[i]][home[u]]++;
        }
    }
    for(int i=1;i<=n;i++){
        adj[i].clear();
    }
    for(auto& u: lis){
        compo[u].clear();
    }
    fa[1]=0;
    for(auto& u: lis){
        int popo=fa[u];
        // cout<<popo<<" ";
        while(popo!=1&&popo!=0){
            // cout<<popo<<" ";
            tot[disc[u]][home[popo]]++;
            popo=fa[popo];
        }
        if(popo==0)continue;
        tot[disc[u]][home[popo]]++;
    }
    while(q--){
        ll a,b;
        cin>>a>>b;
        if(hv[{a,b}]){cout<<ans[{a,b}]<<'\n';continue;};
        ll an=0;
        for(auto& u: reg[b]){
            blk[disc[inside[u]]].pb(u);
        }
        for(auto& u: reg[a]){
            for(auto& k: blk[disc[inside[u]]]){
                if(anc(u,k)){
                    an++;
                }
            }
        }
        for(auto& u: reg[b]){
            blk[disc[inside[u]]].clear();
        }
        ll first=0;
        for(auto& u: lis){
            first+=tot[disc[u]][a]*cnt[disc[u]][b];
        }
        hv[{a,b}]=1,ans[{a,b}]=first+an;
        cout<<first+an<<endl;
    }
}

Compilation message

regions.cpp: In function 'int main()':
regions.cpp:88:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<node>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   88 |     for(int i=0;i<revdep.size();i++){
      |                 ~^~~~~~~~~~~~~~
regions.cpp:128:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  128 |     for(int i=0;i<lis.size();i++){
      |                 ~^~~~~~~~~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 23128 KB Output is correct
2 Correct 4 ms 23176 KB Output is correct
3 Correct 6 ms 23184 KB Output is correct
4 Correct 8 ms 23700 KB Output is correct
5 Correct 10 ms 23464 KB Output is correct
6 Correct 13 ms 24116 KB Output is correct
7 Correct 23 ms 24704 KB Output is correct
8 Correct 28 ms 24324 KB Output is correct
9 Correct 39 ms 25140 KB Output is correct
10 Correct 66 ms 25452 KB Output is correct
11 Correct 98 ms 26084 KB Output is correct
12 Correct 131 ms 26736 KB Output is correct
13 Correct 167 ms 28012 KB Output is correct
14 Correct 232 ms 31532 KB Output is correct
15 Correct 229 ms 35904 KB Output is correct

Subtask #2
80.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1054 ms 41732 KB Output is correct
2 Correct 1296 ms 39716 KB Output is correct
3 Correct 1808 ms 52204 KB Output is correct
4 Correct 242 ms 32936 KB Output is correct
5 Correct 325 ms 36524 KB Output is correct
6 Correct 489 ms 35024 KB Output is correct
7 Correct 631 ms 38404 KB Output is correct
8 Correct 1113 ms 55448 KB Output is correct
9 Correct 2074 ms 66712 KB Output is correct
10 Correct 3483 ms 81476 KB Output is correct
11 Correct 3987 ms 77488 KB Output is correct
12 Correct 4273 ms 65640 KB Output is correct
13 Correct 5063 ms 72592 KB Output is correct
14 Correct 6021 ms 76616 KB Output is correct
15 Correct 7211 ms 88344 KB Output is correct
16 Execution timed out 8086 ms 98380 KB Time limit exceeded
17 Correct 7116 ms 95316 KB Output is correct