제출 #555681

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

race

#include "race.h"
//#include "grader.cpp"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int maxn = 100100;

ll jmp[maxn][25], dis[maxn], depth[maxn], subtree[maxn], par[maxn]; int answ, KK;
set<pair<ll,ll>> adj[maxn];
set<int> sub[maxn];
vector<int> adj2[maxn];
multiset<pair<int,int>> S[maxn];
map<pair<int,int>,int> M;

void dfs(int s, int p, int ok){
    subtree[s]=1;
    if(ok){
        depth[s] = (p==-1?0:depth[p]+1);
        dis[s] = (p==-1?0:dis[p]+M[{p,s}]);
        jmp[s][0] = p;
    }
    for(auto x : adj[s]){
        int u = x.first;
        if(u==p) continue;
        dfs(u,s,ok), subtree[s]+=subtree[u];
    }
}

int find_centroid(int s, int p, int sz){
    for(auto u : adj[s])
        if(u.first!=p and subtree[u.first]>sz/2)
            return find_centroid(u.first, s, sz);
    return s;
}

void make_centroid(int s, int p){
    dfs(s,-1,0); int sz = subtree[s];
    int centroid = find_centroid(s,-1,sz);
    par[centroid]=p;
    if(p!=-1) adj2[p].push_back(centroid);
    while(!adj[centroid].empty()){
        int x = adj[centroid].begin()->first;
        adj[x].erase(adj[x].lower_bound({centroid,-1}));
        adj[centroid].erase(adj[centroid].begin());
        make_centroid(x,centroid);
    }
}

int get_path(int x, int k){
    for(int j = 0; j <= 18; j++)
        if(k&(1<<j) and x!=-1) x = jmp[x][j];
    return x;
}

int lca(int a, int b){
    if(a==b) return a;
    if(jmp[a][0]==jmp[b][0]) return jmp[a][0];
    if(depth[a]>depth[b]) swap(a,b);
    if(depth[a]<depth[b]) return lca(a,get_path(b,depth[b]-depth[a]));
    for(int j = 18; j >= 0; j--)
        if(jmp[a][j]!=-1 and jmp[a][j]!=jmp[b][j])
            return lca(jmp[a][j], jmp[b][j]);
}

ll dist(int a, int b){
    return dis[a]+dis[b]-2*dis[lca(a,b)];
}

int len(int a, int b){
    return depth[a]+depth[b]-2*depth[lca(a,b)];
}

void Merge(set<int> &S, set<int> &SS){
    if(S.size()<SS.size()) S.swap(SS);
    for(auto u : SS) S.insert(u);
}

void DFS(int s, int p, int Anc, bool ok){
    sub[s].insert(s);
    for(auto u : adj2[s]){
        if(u==p) continue;
        DFS(u,s,s,0);
        for(auto w : sub[u]){
            int X = Anc; if(X==-1) X = s;
            int D = dist(X,w);
            if(KK-D==0) { answ = min(answ, len(X,w)); continue; }
            auto itr = S[X].lower_bound({KK-D,-1});
            if(itr!=S[X].end() and itr->first==KK-D)
                answ = min(answ, len(X,w)+itr->second);
        }
        Merge(sub[s], sub[u]);
        DFS(u,s,s,1);
    }
    for(auto u : adj2[s]) if(u!=p) DFS(u,s,-1,0);
    if(Anc==-1) return;
    if(ok) S[Anc].insert({dist(Anc,s),len(Anc,s)});
    else S[Anc].erase(S[Anc].find({dist(Anc,s),len(Anc,s)}));
}

int best_path(int N, int K, int H[][2], int L[])
{
    answ = N+1;
    for(int i = 0; i < N-1; i++)
        adj[++H[i][0]].insert({++H[i][1],L[i]}),
        adj[H[i][1]].insert({H[i][0],L[i]}),
        M[{H[i][0],H[i][1]}]=M[{H[i][1],H[i][0]}]=L[i];
    memset(jmp, -1, sizeof(jmp));
    dfs(1,-1,1); make_centroid(1,-1);
    for(int j = 1; j <= 18; j++)
        for(int i = 1; i <= N; i++)
            if(jmp[i][j-1]!=-1) jmp[i][j] = jmp[jmp[i][j-1]][j-1];
    for(int i = 1; i <= N; i++){
        int x = i;
        while(x!=-1){
            S[x].insert({dist(i,x),len(i,x)});
            x = par[x];
        }
    }
    DFS(1,-1,-1,0);
    /*
    cout << "\n\n";
    for(int i = 0; i < N-1; i++)
        cout << H[i][0] << " " << H[i][1] << " " << L[i] << "\n";
    cout << "\n\n";*/
    return (answ==N+1?-1:answ);
}

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

race.cpp: In function 'int lca(int, int)':
race.cpp:63:1: warning: control reaches end of non-void function [-Wreturn-type]
   63 | }
      | ^

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