oj.uz

답안 #958004

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

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 7 ms 24152 KB Output is correct
2 Correct 6 ms 24352 KB Output is correct
3 Correct 5 ms 24356 KB Output is correct
4 Correct 8 ms 24360 KB Output is correct
5 Correct 9 ms 24900 KB Output is correct
6 Correct 15 ms 24992 KB Output is correct
7 Correct 27 ms 25204 KB Output is correct
8 Correct 25 ms 25796 KB Output is correct
9 Correct 43 ms 25812 KB Output is correct
10 Correct 70 ms 28812 KB Output is correct
11 Correct 102 ms 31240 KB Output is correct
12 Correct 109 ms 34408 KB Output is correct
13 Correct 150 ms 34508 KB Output is correct
14 Correct 210 ms 36500 KB Output is correct
15 Correct 240 ms 47004 KB Output is correct

Subtask #2
70.0 / 85.0

# 결과 실행 시간 메모리 Grader output
1 Correct 925 ms 58912 KB Output is correct
2 Correct 1127 ms 56684 KB Output is correct
3 Correct 1646 ms 73872 KB Output is correct
4 Correct 233 ms 38372 KB Output is correct
5 Correct 349 ms 45048 KB Output is correct
6 Correct 513 ms 48984 KB Output is correct
7 Correct 646 ms 54348 KB Output is correct
8 Correct 1177 ms 81396 KB Output is correct
9 Correct 2510 ms 104508 KB Output is correct
10 Correct 4075 ms 125704 KB Output is correct
11 Correct 4463 ms 123572 KB Output is correct
12 Correct 4229 ms 110272 KB Output is correct
13 Correct 5400 ms 116620 KB Output is correct
14 Correct 6380 ms 121000 KB Output is correct
15 Runtime error 6171 ms 131072 KB Execution killed with signal 9
16 Runtime error 1384 ms 131072 KB Execution killed with signal 9
17 Runtime error 2436 ms 131072 KB Execution killed with signal 9