oj.uz

답안 #958018

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
958018 2024-04-04T16:38:49 Z tosivanmak Regions (IOI09_regions) C++17
70 / 100
 5899 ms 131072 KB 
#include<bits/stdc++.h>
using namespace std;
#define ll int
#define pb push_back
const ll B=400;
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[501];
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[501][25001];
ll tot[501][25001];

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

Subtask #1
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 22872 KB Output is correct
2 Correct 4 ms 23080 KB Output is correct
3 Correct 5 ms 23088 KB Output is correct
4 Correct 7 ms 23344 KB Output is correct
5 Correct 8 ms 23112 KB Output is correct
6 Correct 16 ms 23452 KB Output is correct
7 Correct 21 ms 23492 KB Output is correct
8 Correct 28 ms 24644 KB Output is correct
9 Correct 48 ms 25344 KB Output is correct
10 Correct 76 ms 28984 KB Output is correct
11 Correct 114 ms 30148 KB Output is correct
12 Correct 119 ms 34656 KB Output is correct
13 Correct 151 ms 34972 KB Output is correct
14 Correct 188 ms 39328 KB Output is correct
15 Correct 254 ms 52100 KB Output is correct

Subtask #2
55.0 / 85.0

# 결과 실행 시간 메모리 Grader output
1 Correct 979 ms 65768 KB Output is correct
2 Correct 1049 ms 64248 KB Output is correct
3 Correct 1680 ms 81344 KB Output is correct
4 Correct 234 ms 40480 KB Output is correct
5 Correct 333 ms 48584 KB Output is correct
6 Correct 528 ms 51824 KB Output is correct
7 Correct 712 ms 59416 KB Output is correct
8 Correct 1327 ms 90584 KB Output is correct
9 Correct 2848 ms 115932 KB Output is correct
10 Runtime error 2447 ms 131072 KB Execution killed with signal 9
11 Runtime error 3585 ms 131072 KB Execution killed with signal 9
12 Correct 4598 ms 123208 KB Output is correct
13 Correct 5899 ms 131072 KB Output is correct
14 Runtime error 4374 ms 131072 KB Execution killed with signal 9
15 Runtime error 206 ms 131072 KB Execution killed with signal 9
16 Runtime error 255 ms 131072 KB Execution killed with signal 9
17 Runtime error 238 ms 131072 KB Execution killed with signal 9