Submission #223362

#	Time	Username	Problem	Language	Result	Execution time	Memory
223362		wendy_virgo	Race (IOI11_race)	C++14	100 / 100	1075 ms	80972 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 h[LOG_N][2*N],idx[N],tin[N],tme,st[N],d[N];
vector<int> events;
int64_t s[N];
bool del[N];
int sz[N],ans=INF,f[K];

void DFS_LCA(int u,int fa){
    idx[tin[u]=tme++]=u;
    st[u]=events.size();
    events.push_back(tin[u]);
    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;
            DFS_LCA(v,u);
            events.push_back(tin[u]);
        }
    }
}

void BuildLCA(){
    DFS_LCA(1,-1);
    for(int i=0;i<events.size();++i){
        h[0][i]=events[i];
    }
    for(int i=1;i<LOG_N;++i){
        for(int j=1;j+(1<<i-1)<events.size();++j){
            h[i][j]=min(h[i-1][j],h[i-1][j+(1<<i-1)]);
        }
    }
}

int Query(int u,int v){
    int l=u==v?0:__lg(v-u);
    return min(h[l][u],h[l][v-(1<<l)+1]);
}

int LCA(int u,int v){
    if(st[u]>st[v]){
        swap(u,v);
    }
    return idx[Query(st[u],st[v])];
}

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_Reset(int u,int r){
    int64_t id=WeightDist(u,r);
    if(id<K){
        f[id]=INF;
    }
    for(int v:ct[u]){
        DFS_Reset(v,r);
    }
}

void DFS_UpdateAns(int u,int r){
    int64_t id=WeightDist(u,r);
    if(id<=k&&f[k-id]!=INF){
        ans=min(ans,EdgeDist(u,r)+f[k-id]);
    }
    for(int v:ct[u]){
        DFS_UpdateAns(v,r);
    }
}

void DFS_UpdateF(int u,int r){
    int64_t id=WeightDist(u,r);
    if(id<=k){
        f[id]=min(f[id],EdgeDist(u,r));
    }
    for(int v:ct[u]){
        DFS_UpdateF(v,r);
    }
}

void Calc(int u){
    for(int v:ct[u]){
        f[0]=0;
        DFS_UpdateAns(v,u);
        DFS_UpdateF(v,u);
    }
    DFS_Reset(u,u);
}

int Solve(){
    BuildLCA();
	BuildCentroidTree(1);
	for(int i=0;i<K;++i){
        f[i]=INF;
	}
	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,w;
//        cin>>u>>v>>w;
//        u++;
//        v++;
////        cout<<u<<' '<<v<<'\n';
//        g[u].push_back(i);
//        g[v].push_back(i);
//        edgeList[i]={u,v,w};
//	}
////	for(int i=1;i<=n-1;++i){
////        cin>>edgeList[i].w;
////	}
//	cout<<Solve();
//    return 0;
//}

Compilation message (stderr)

race.cpp: In function 'void BuildLCA()':
race.cpp:58:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<events.size();++i){
                 ~^~~~~~~~~~~~~~
race.cpp:62:28: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
         for(int j=1;j+(1<<i-1)<events.size();++j){
                           ~^~
race.cpp:62:31: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int j=1;j+(1<<i-1)<events.size();++j){
                     ~~~~~~~~~~^~~~~~~~~~~~~~
race.cpp:63:49: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
             h[i][j]=min(h[i-1][j],h[i-1][j+(1<<i-1)]);
                                                ~^~

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