Submission #283591

#	Time	Username	Problem	Language	Result	Execution time	Memory
283591		aloo123	Race (IOI11_race)	C++14	0 / 100	31 ms	47352 KiB

race

		
#include <bits/stdc++.h>
#define ll long long int
#define vi vector<int>
#define vll vector<ll>
#define vvi vector < vi >
#define pii pair<int,int>
#define pll pair<long long, long long>
#define mod 1000000007
#define inf 9999999999;
#define all(c) c.begin(),c.end()
#define mp(x,y) make_pair(x,y)
#define pb push_back
#define in insert
#define f first
#define s second
#define pi 3.141592653589793238
using namespace std;
const int MAXN = 1e6+5;
const int INF = 1e7;
int n,k;	
set<int>adj[MAXN];
map<pair<int,int>,int> wt;
int sz[MAXN];
int currsize;
int ans;
int cnt[MAXN];
int glob[MAXN];
void dfs(int u,int p){
	sz[u] = 1;
	currsize++;
	for(auto v:adj[u]){
		if(v != p){
			dfs(v,u);
			sz[u] += sz[v];
		}
	}
}
int dfs2(int u,int p){
	for(auto v:adj[u]){
		if(v != p && sz[v] > currsize/2){
			return dfs2(v,u);
		}
	}
	return u;
	
}
void dfs3(int u,int p,int sum,int dep){
	if(sum <= k){
		cnt[sum] = min(cnt[sum],dep);
		if(glob[k-sum] != -1)
			ans = min(ans,glob[k-sum] + cnt[sum]);
	}
	for(auto v:adj[u]){
		if(v != p){
			dfs3(v,u,sum + wt[{u,v}],dep+1);
		}
	}
}
void decompose(int u,int p){
	currsize=0;
	dfs(u,p);
	int c = dfs2(u,p);
	for(auto v:adj[c]){
		for(int i =1;i<=k;i++) cnt[i]  =n+1;
		dfs3(v,c,wt[{c,v}],1);
		for(int i =1;i<=k;i++) {
			if(cnt[i] == (n+1)) continue;
			if(glob[i] != -1)
				glob[i] = min(glob[i],cnt[i]);
			else glob[i] = cnt[i];
		}
	}
	// look in the subtree of c

	for(auto v:adj[c]){
		adj[v].erase(c);
		decompose(v,c);
	}
			adj[c].clear();

}
int best_path(int N, int K, int H[][2], int L[]){
	n = N;
	k = K;
	ans = n+1;
	for(int i = 0;i<N-1;i++){
		int u = H[i][0];
		int v = H[i][1];
		u++;
		v++;
		int w = L[i];
		wt[{u,v}] = w;
		wt[{v,u}] = w;
		adj[u].in(v);
		adj[v].in(u);
	}
	for(int i =1;i<=k;i++) glob[i] = -1;
	decompose(1,-1);
	// for(int i = 1;i<=k;i++) cout << glob[i] << endl; 
	if(ans == (n+1)) ans = -1;
	return ans;
	// cout << ans << endl;
}

// int main()
// {
// 	std::ios::sync_with_stdio(false);
// 	int h[10][2];
// 	h[0][0] = 0;
// 	h[0][1] = 1;

// 	h[1][0] = 0;
// 	h[1][1] = 2;

// 	h[2][0] = 2;
// 	h[2][1] = 3;

// 	h[3][0] = 3;
// 	h[3][1] = 4;

// 	h[4][0] = 4;
// 	h[4][1] = 5;

// 	h[5][0] = 0;
// 	h[5][1] = 6;

// 	h[6][0] = 6;
// 	h[6][1] = 7;

// 	h[7][0] = 6;
// 	h[7][1] = 8;

// 	h[8][0] = 8;
// 	h[8][1] = 9;
// 	h[9][0 ] = 8;
// 	h[9][1] = 10;



// 	int l[10];
// 	l[0] = 3;
// 	l[1] = 4;
// 	l[2] = 5;

// 	l[3] = 4;
// 	l[4] = 6;
// 	l[5] = 3;


// 	l[6] = 2;
// 	l[7] = 5;
// 	l[8] = 6;
// 	l[9] = 7;

// 	int h2[2][2];
// 	h2[0][0]  =0;
// 	h2[0][1] = 1;
// 	h2[1][0] =1;
// 	h2[1][1] = 2;
// 	int l2[2];
// 	l2[0] = 1;
// 	l2[1] = 1;

// 	cout << best_path(11,12,h,l) << endl;
// 	// cin >> n;
// 	// cin >> k;
// 	// for(int i =2;i<=n;i++){
// 	// 	int u,v;
// 	// 	cin >> u >> v;
// 	// 	int w;
// 	// 	cin >> w;
// 	// 	wt[{u,v}] = w;
// 	// 	wt[{v,u}] = w;
// 	// 	adj[u].in(v);
// 	// 	adj[v].in(u);
// 	// }
// 	// for(int i =1;i<=k;i++) glob[i] = INF;
// 	// decompose(1,-1);
// 	// // for(int i = 1;i<=k;i++) cout << glob[i] << endl;
// 	// if(ans == INF) ans = -1;
// 	// cout << ans << endl;
	
// 	return 0;
// }

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