제출 #966941

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
966941		jhinezeal123	경주 (Race) (IOI11_race)	C++17	0 / 100	3057 ms	29020 KiB

race

#include <bits/stdc++.h>
#define ii pair<int, int>
#define iii pair<int,ii>
#define vii vector<ii>
#define fi first
#define se second
#define endl '\n'
#define show(T) {for (auto x:T) cout<<x<<' ';cout<<endl;}
using namespace std;
const double eps = 0.0000001;
const int mod1 = 998244353,mod2 = 1e9+7,mod = 1337377;
const int N = 200005;
const int MATRIX_SIZE = 64;
int n,pa[N][20],dis[N][20],h[N],child[N],k,pct[N],ans=1e18;
vector <ii> G[N];
vector <int> g[N];
map <int,int> mp[N];
map <int,int>::iterator it;
bool chosen[N];
void DFS(int p,int v){
    pa[v][0]=p;
    h[v]=h[p]+1;
    for (auto x:G[v]){
        if (x.fi==p) continue;
        dis[x.fi][0]=x.se;
        DFS(v,x.fi);
    }
}
void init(){
    for (int i=1;i<=17;++i){
        for (int j=1;j<=n;++j){
            pa[j][i]=pa[pa[j][i-1]][i-1];
            dis[j][i]=dis[j][i-1]+dis[pa[j][i-1]][i-1];
        }
    }
}
ii LCA(int a,int b){
    ii res={0,0};
    if (h[a]<h[b]) swap(a,b);
    int cl=h[a]-h[b];
    for (int i=log2(cl);i>=0;--i){
        if (cl>=1<<i){
            cl-=1<<i;
            res.fi+=1<<i;
            res.se+=dis[a][i];
            a=pa[a][i];
        }
    }
    if (a==b) return res;
    for (int i=log2(h[a]);i>=0;--i){
        if (pa[a][i]!=pa[b][i]){
            res.fi+=2<<i;
            res.se+=dis[a][i]+dis[b][i];
            a=pa[a][i];
            b=pa[b][i];
        }
    }
    return {res.fi+2,res.se+dis[a][0]+dis[b][0]};
}
void DFS2(int p,int v){
    child[v]=1;
    for (auto x:G[v]){
        if (x.fi==p||chosen[x.fi]) continue;
        DFS2(v,x.fi);
        child[v]+=child[x.fi]; 
    }
}
int centroid(int p,int v,int sl){
    for (auto x:G[v]){
        if (x.fi==p||chosen[x.fi]) continue;
        if (child[x.fi]-1>=sl>>1) return centroid(v,x.fi,sl);
    }
    return v;
}
int build(int v){
    DFS2(0,v);
    v=centroid(0,v,child[v]);
    chosen[v]=true;
    for (auto x:G[v]){
        if (chosen[x.fi]) continue;
        int tam=build(x.fi);
        // cout<<tam<<' '<<v<<endl;
        g[v].push_back(tam);
        pct[tam]=v;
    }
    return v;
}
void up(int v,int cur){
    ii tam=LCA(v,cur);
    it=mp[cur].find(k-tam.se);
    if (it!=mp[cur].end()) ans=min(ans,tam.fi+it->se);
    it=mp[cur].emplace(tam.se,tam.fi).fi;
    it->se=min(it->se,tam.fi);
    if (pct[cur]) up(v,pct[cur]);
}
int best_path(int _n, int _k, int (*H)[2], int *L){
    // cin>>n>>k;
    n=_n;
    k=_k;
    for (int i=1;i<n;++i){
        G[H[i][0]].push_back({H[i][1]+1,L[i]});
        G[H[i][1]].push_back({H[i][0]+1,L[i]});
    }
    DFS(0,1);
    init();
    build(1);
    for (int i=1;i<=n;++i) up(i,i);
    return ans==1e18?-1:ans;
}

컴파일 시 표준 에러 (stderr) 메시지

race.cpp:14:55: warning: overflow in conversion from 'double' to 'int' changes value from '1.0e+18' to '2147483647' [-Woverflow]
   14 | int n,pa[N][20],dis[N][20],h[N],child[N],k,pct[N],ans=1e18;
      |                                                       ^~~~

• Subtask 1: 0 / 9
• Subtask 2: 0 / 12
• Subtask 3: 0 / 22
• Subtask 4: 0 / 57