제출 #1304146

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1304146		orkag	Race (IOI11_race)	C++20	9 / 100	54 ms	7660 KiB

race

#include "race.h"
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define pb push_back
#define F first
#define S second
#define pii pair<int,int>
#define vi vector<int>
#define vpii vector<pii>

#define loop(i,n) sloop(0,i,n)
#define sloop(s, i, n) for(int i=(s);i<(n);i++)
#define rloop(i,n) rsloop(0,i,n)
#define rsloop(s,i,n) for(int i=(n);i-->(s);)

#define all(v) (v).begin(),(v).end()

#define nie {cout<<"No\n";return;}
#define tak {cout<<"Yes\n";return;}

#ifdef DEBUG
#define DBG cout << __LINE__ << endl;
#else 
#define DBG
#endif 

//int xses[8] = {-1,1,0,0,-1,1,1,-1};
//int yses[8] = {0,0,-1,1,-1,1,-1,1};

//#define int ll

vector<vpii> graf;
int k;
int res = INT_MAX;

pair<pii,map<int,int>> dfs(int node,int p=-1){

	pair<pii,map<int,int>> cur;
	cur.F = {0,0};

	for(pii i:graf[node]){
		if(i.F==p)continue;
		if(i.S==k){
			res=1;
		}
		
		auto [chng,a] = dfs(i.F,node);
		chng.F+=i.S;chng.S++;
		a[i.S-chng.F]=1-chng.S;
		if(cur.S.size()<a.size()){
			swap(cur.S,a);
			swap(chng,cur.F);
		}

		for(pii j:a){
			if(cur.S.count(k-(j.F+chng.F))){
				res = min(res,j.S+chng.S+cur.S[k-(j.F+chng.F)]+cur.F.S);
			}
		}

		/*
		cout<<node<<'\n';
		for(pii z:cur.S){
			cout<<z.F+cur.F.F<<' '<<z.S+cur.F.S<<'\n';
		}

		cout<<node<<'\n';
		for(pii j:a){
			cout<<j.F+chng.F<<' '<<j.S+chng.S<<'\n';
		}
		
*/
		for(pii j:a){
			int u = j.F+chng.F - cur.F.F;
			int v = j.S+chng.S - cur.F.S;

			if(cur.S.count(u)){
				cur.S[u]=min(cur.S[u],v);
			}else{
				cur.S[u]=v;
			}
		}

	}

	if(cur.S.count(k-cur.F.F)){
		res=min(res,cur.S[k-cur.F.F]+cur.F.S);
	}
	/*
	for(pii i:cur.S){
		cout<<i.F+cur.F.F<<' '<<i.S+cur.F.S<<'\n';
	}
	*/

	return cur;
}

int best_path(int N, int K, int H[][2], int L[])
{
	int n = N;
	k = K;
	graf.assign(n,vpii());
	loop(i,n-1){
		int a = H[i][0];
		int b = H[i][1];
		int w = L[i];
		graf[a].pb({b,w});
		graf[b].pb({a,w});
	}

	dfs(0);

	if(res==INT_MAX)res=-1;
  	return res;
}

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