oj.uz

답안 #958006

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

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 5 ms 24152 KB Output is correct
2 Correct 5 ms 24344 KB Output is correct
3 Correct 5 ms 24352 KB Output is correct
4 Correct 7 ms 24868 KB Output is correct
5 Correct 9 ms 25144 KB Output is correct
6 Correct 16 ms 24804 KB Output is correct
7 Correct 22 ms 25524 KB Output is correct
8 Correct 24 ms 25472 KB Output is correct
9 Correct 37 ms 25512 KB Output is correct
10 Correct 61 ms 28428 KB Output is correct
11 Correct 99 ms 30856 KB Output is correct
12 Correct 114 ms 34424 KB Output is correct
13 Correct 148 ms 35940 KB Output is correct
14 Correct 199 ms 38984 KB Output is correct
15 Correct 256 ms 48744 KB Output is correct

Subtask #2
45.0 / 85.0

# 결과 실행 시간 메모리 Grader output
1 Correct 935 ms 63144 KB Output is correct
2 Correct 1093 ms 61240 KB Output is correct
3 Correct 1645 ms 78180 KB Output is correct
4 Correct 244 ms 40272 KB Output is correct
5 Correct 319 ms 47396 KB Output is correct
6 Correct 508 ms 51232 KB Output is correct
7 Correct 671 ms 56340 KB Output is correct
8 Correct 1292 ms 85104 KB Output is correct
9 Correct 2581 ms 108816 KB Output is correct
10 Incorrect 4080 ms 131072 KB Output isn't correct
11 Incorrect 4752 ms 129996 KB Output isn't correct
12 Incorrect 4491 ms 116160 KB Output isn't correct
13 Incorrect 5455 ms 124740 KB Output isn't correct
14 Incorrect 6434 ms 127248 KB Output isn't correct
15 Runtime error 3039 ms 131072 KB Execution killed with signal 9
16 Runtime error 249 ms 131072 KB Execution killed with signal 9
17 Runtime error 330 ms 131072 KB Execution killed with signal 9