Submission #223317

#	Time	Username	Problem	Language	Result	Execution time	Memory
223317		wendy_virgo	Race (IOI11_race)	C++14	21 / 100	3086 ms	90916 KiB

race

#include <bits/stdc++.h>

using namespace std;

template<typename TH>
void _dbg(const char* sdbg, TH h)
{
	cerr << sdbg << " = " << h << "\n";
}

template<typename TH, typename... TA>
void _dbg(const char* sdbg, TH h, TA... t)
{
	while (*sdbg != ',') cerr << *sdbg++;
	cerr << " = " << h << ",";
	_dbg(sdbg + 1, t...);
}

#define db(...) _dbg(#__VA_ARGS__, __VA_ARGS__)
#define chkpt cerr << "--- Checkpoint here ---\n";

const int N=2e5+5,K=1e6+6,INF=1e9,LOG_N=20;

struct Edge{
    int u,v,w;

    int Adj(int x){
        return u^v^x;
    }
};

int n,k;
Edge edgeList[N];
vector<int> g[N],ct[N];
int d[N],p[LOG_N][N];
int64_t s[N];
bool del[N];
int sz[N],ans=INF;
multiset<int> ms[K];

void DFS_LCA(int u,int fa){
    for(int id:g[u]){
        int v=edgeList[id].Adj(u),w=edgeList[id].w;
        if(v!=fa){
            d[v]=d[u]+1;
            s[v]=s[u]+w;
            p[0][v]=u;
            DFS_LCA(v,u);
        }
    }
}

void BuildLCA(){
    memset(p,-1,sizeof p);
    DFS_LCA(1,-1);
    for(int i=1;i<LOG_N;++i){
        for(int j=1;j<=n;++j){
            if(~p[i-1][j]){
                p[i][j]=p[i-1][p[i-1][j]];
            }
        }
    }
}

int LCA(int u,int v){
    if(d[u]<d[v]){
        swap(u,v);
    }
    for(int i=LOG_N-1;i>=0;--i){
        if(~p[i][u]&&d[p[i][u]]>=d[v]){
            u=p[i][u];
        }
    }
    if(u==v){
        return u;
    }
    for(int i=LOG_N-1;i>=0;--i){
        if(~p[i][u]&&p[i][u]!=p[i][v]){
            u=p[i][u];
            v=p[i][v];
        }
    }
    return p[0][u];
}

int EdgeDist(int u,int v){
    return d[u]+d[v]-2*d[LCA(u,v)];
}

int64_t WeightDist(int u,int v){
    return s[u]+s[v]-2*s[LCA(u,v)];
}

void DFS_Size(int u,int fa){
    sz[u]=1;
    for(int id:g[u]){
        int v=edgeList[id].Adj(u);
        if(v!=fa&&!del[v]){
            DFS_Size(v,u);
            sz[u]+=sz[v];
        }
    }
}

int FindCentroid(int u,int fa,int curSz){
    int maxSize=0,big=0;
    for(int id:g[u]){
        int v=edgeList[id].Adj(u);
        if(v!=fa&&!del[v]&&sz[v]>maxSize){
            maxSize=sz[v];
            big=v;
        }
    }
    if(maxSize<=curSz/2){
        return u;
    }
    return FindCentroid(big,u,curSz);
}

int BuildCentroidTree(int u){
    DFS_Size(u,-1);
    int cen=FindCentroid(u,-1,sz[u]);
    del[cen]=true;
    for(int id:g[cen]){
        int v=edgeList[id].Adj(cen);
        if(!del[v]){
            int tmp=BuildCentroidTree(v);
            ct[cen].push_back(tmp);
//            cout<<cen<<' '<<tmp<<'\n';
        }
    }
    return cen;
}

void DFS_Add(int u,int r){
    int64_t id=WeightDist(u,r);
    if(id<K){
        ms[id].insert(EdgeDist(u,r));
    }
    for(int v:ct[u]){
        DFS_Add(v,r);
    }
}

void DFS_Remove(int u,int r){
    int64_t id=WeightDist(u,r);
    if(id<K){
        ms[id].erase(ms[id].find(EdgeDist(u,r)));
    }
    for(int v:ct[u]){
        DFS_Remove(v,r);
    }
}

void DFS_Update(int u,int r){
    int64_t id=WeightDist(u,r);
    if(id<=k){
        if(ms[k-id].size()>0){
            ans=min(ans,EdgeDist(u,r)+*ms[k-id].begin());
        }
    }
    for(int v:ct[u]){
        DFS_Update(v,r);
    }
}

void Calc(int u){
    DFS_Add(u,u);
    for(int v:ct[u]){
        DFS_Remove(v,u);
        DFS_Update(v,u);
        DFS_Add(v,u);
    }
    DFS_Remove(u,u);
}

int Solve(){
    BuildLCA();
	BuildCentroidTree(1);
	for(int i=1;i<=n;++i){
        Calc(i);
	}
	return ans==INF?-1:ans;
}

int best_path(int N,int K,int H[][2],int L[])
{
    n=N;
    k=K;
    for(int i=0;i<=n-2;++i){
        int u=H[i][0]+1,v=H[i][1]+1;
        g[u].push_back(i+1);
        g[v].push_back(i+1);
        edgeList[i+1]={u,v,0};
    }
    for(int i=0;i<=n-2;++i){
        edgeList[i+1].w=L[i];
    }
    return Solve();
}

//int main()
//{
//    freopen("IOI11_race.inp","r",stdin);
//	ios_base::sync_with_stdio(0);
//	cin.tie(0);
//	cin>>n>>k;
//	for(int i=1;i<=n-1;++i){
//        int u,v;
//        cin>>u>>v;
//        u++;
//        v++;
////        cout<<u<<' '<<v<<'\n';
//        g[u].push_back(i);
//        g[v].push_back(i);
//        edgeList[i]={u,v,0};
//	}
//	for(int i=1;i<=n-1;++i){
//        cin>>edgeList[i].w;
//	}
//	cout<<Solve();
//    return 0;
//}

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