Submission #223370

#	Time	Username	Problem	Language	Result	Execution time	Memory
223370		wendy_virgo	경주 (Race) (IOI11_race)	C++14	100 / 100	1025 ms	33400 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];
bool del[N];
int sz[N],ans=INF,f[K];

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);
}

void DFS_UpdateAns(int u,int fa,int64_t s,int d){
    if(s<=k&&f[k-s]!=INF){
        ans=min(ans,f[k-s]+d);
    }
    for(int id:g[u]){
        int v=edgeList[id].Adj(u),w=edgeList[id].w;
        if(!del[v]&&v!=fa){
            DFS_UpdateAns(v,u,s+w,d+1);
        }
    }
}

void DFS_UpdateF(int u,int fa,int64_t s,int d){
    if(s<=k){
        f[s]=min(f[s],d);
    }
    for(int id:g[u]){
        int v=edgeList[id].Adj(u),w=edgeList[id].w;
        if(!del[v]&&v!=fa){
            DFS_UpdateF(v,u,s+w,d+1);
        }
    }
}

void DFS_Reset(int u,int fa,int64_t s,int d){
    if(s<=k){
        f[s]=INF;
    }
    for(int id:g[u]){
        int v=edgeList[id].Adj(u),w=edgeList[id].w;
        if(!del[v]&&v!=fa){
            DFS_Reset(v,u,s+w,d+1);
        }
    }
}

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

int Solve(){
    for(int i=0;i<K;++i){
        f[i]=INF;
	}
	BuildCentroidTree(1);
	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 'int BuildCentroidTree(int)':
race.cpp:116:17: warning: unused variable 'tmp' [-Wunused-variable]
             int tmp=BuildCentroidTree(v);
                 ^~~

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