oj.uz

답안 #958008

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
958008 2024-04-04T16:15:46 Z tosivanmak Regions (IOI09_regions) C++17
85 / 100
 5892 ms 131072 KB 
#include<bits/stdc++.h>
using namespace std;
#define ll int
#define pb push_back
const ll B=1200;
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[155];
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[155][25005];
ll tot[155][25005];
ll store[155];

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

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 22872 KB Output is correct
2 Correct 4 ms 23084 KB Output is correct
3 Correct 5 ms 23336 KB Output is correct
4 Correct 6 ms 23096 KB Output is correct
5 Correct 8 ms 23624 KB Output is correct
6 Correct 16 ms 24292 KB Output is correct
7 Correct 24 ms 24108 KB Output is correct
8 Correct 29 ms 24444 KB Output is correct
9 Correct 46 ms 24548 KB Output is correct
10 Correct 61 ms 27184 KB Output is correct
11 Correct 103 ms 27640 KB Output is correct
12 Correct 120 ms 31120 KB Output is correct
13 Correct 143 ms 30804 KB Output is correct
14 Correct 259 ms 31584 KB Output is correct
15 Correct 235 ms 37320 KB Output is correct

Subtask #2
70.0 / 85.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1024 ms 45172 KB Output is correct
2 Correct 1208 ms 43980 KB Output is correct
3 Correct 1631 ms 54788 KB Output is correct
4 Correct 238 ms 32604 KB Output is correct
5 Correct 350 ms 38540 KB Output is correct
6 Correct 461 ms 39096 KB Output is correct
7 Correct 664 ms 40396 KB Output is correct
8 Correct 1068 ms 59932 KB Output is correct
9 Correct 2097 ms 71116 KB Output is correct
10 Correct 3552 ms 87076 KB Output is correct
11 Correct 4030 ms 83848 KB Output is correct
12 Correct 4124 ms 71612 KB Output is correct
13 Correct 4883 ms 76360 KB Output is correct
14 Correct 5892 ms 78536 KB Output is correct
15 Runtime error 2323 ms 131072 KB Execution killed with signal 9
16 Runtime error 2352 ms 131072 KB Execution killed with signal 9
17 Runtime error 2358 ms 131072 KB Execution killed with signal 9