제출 #223282

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
223282		wendy_virgo	경주 (Race) (IOI11_race)	C++14	21 / 100	3067 ms	22420 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;

struct Edge{
    int u,v,w;

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

int n,k;
Edge edgeList[N];
vector<int> g[N];
int d[5005][5005],f[5005][5005];

void DFS(int u,int fa,int r){
    for(int id:g[u]){
        int v=edgeList[id].Adj(u);
        if(v!=fa){
            d[r][v]=d[r][u]+edgeList[id].w;
            f[r][v]=f[r][u]+1;
            DFS(v,u,r);
        }
    }
}

int Sub2(){
    for(int i=1;i<=n;++i){
        DFS(i,-1,i);
    }
    int res=INF;
    for(int i=1;i<=n;++i){
        for(int j=i+1;j<=n;++j){
            if(d[i][j]==k){
                res=min(res,f[i][j]);
            }
        }
    }
    return (res==INF?-1:res);
}

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

//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++;
//        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;
//	}
//	Sub2();
//    return 0;
//}

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