Submission #369595

#	Time	Username	Problem	Language	Result	Execution time	Memory
369595		Pulgster	Race (IOI11_race)	C++17	0 / 100	5 ms	6636 KiB

race

#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#pragma GCC optimization ("unroll-loops")
#include "race.h"
#include <bits/stdc++.h> 
using namespace std;
typedef long long ll;
#define imie(...) " [" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] "
#define ed <<endl;
int N;
int K;
int cur = -1;
const int mxn = 200005;
vector<vector<pair<int, int>>> adj(mxn);
vector<int> sz(mxn);
vector<int> forb(mxn);
int findCentroid(int n, int node, int par){
	// cerr << imie(node) imie(par) ed;
	if(n == 1){
		cur = node;
		return 0;
	}
 	sz[node] = 1;
 	bool ok = 1;
 	for(int i=0;i<(int)adj[node].size();i++){
 		if(cur != -1){
 			return 0;
 		}
 		int v=adj[node][i].first;
 		assert(v < forb.size());
 		if(v != par && !forb[v]){
 			sz[node] += findCentroid(n, v, node);
 			if(sz[v] > n / 2) ok = 0;
 		}
 	}
 	if(n - sz[node] > n / 2){
 		ok = 0;
 	}
 	if(ok){
 		cur = node;
 	}
 	return sz[node];
}

int ans = 2e5+5;
void dfs(int node, int par, int dist, int cost, map<int, int> &global){
	return;
	int k=K;
	if(cost > K){
		return;
	}
	if(cost == k){
		ans = min(ans, dist);
		return;
	}
	if(global[k-cost] != 0){
		ans = min(ans, global[k-cost]+dist);
	}
	for(int i=0;i<(int)adj[node].size();i++){
		int v = adj[node][i].first;
		if(!forb[v] && v != par){
			dfs(v,par,dist+1,cost+adj[node][i].second, global);
		}
	}
	if(global[cost] == 0){
		global[cost] = dist;
	}
	global[cost] = min(global[cost], dist);
}
void mysol(int node){
	int cnt = 0;
	if(forb[node]){
		return;
	}
	function<void(int, int)> mdfs = [&](int curnode, int par){
		// cerr << imie(curnode) imie(par) imie(node) ed;
		cnt++;
		assert(curnode < adj.size());
		for(int i=0;i<(int)adj[curnode].size();i++){
			int v = adj[curnode][i].first;
			assert(v < forb.size());
			if(!forb[v] && v != par){
				mdfs(v, curnode);
			}
		}
	};
	mdfs(node, -1);
	map<int, int> global;
	cur = -1;
	findCentroid(cnt, node, -1);
	forb[cur] = 1;
	dfs(cur, -1, 0, 0, global);
	// cerr << imie(cur) imie(cnt) ed;
	int me = cur;
	for(int i=0;i<(int)adj[me].size();i++){
		return;
		int v = adj[me][i].first;
		if(!forb[v]){
			mysol(v);
		}
	}
}
int best_path(int n, int k, int h[][2], int l[]){
	N=n;
	K=k;
 	for(int i =0;i<n-1;i++){
 		int u = h[i][0];
 		int v = h[i][1];
 		adj[u].push_back({v, l[i]});
 		adj[v].push_back({u, l[i]});
 	}
 	mysol(0);
 	return (ans > n ? -1 : ans);
}

Compilation message (stderr)

race.cpp:3: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
    3 | #pragma GCC optimization ("unroll-loops")
      | 
In file included from /usr/include/c++/9/cassert:44,
                 from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:33,
                 from race.cpp:5:
race.cpp: In function 'int findCentroid(int, int, int)':
race.cpp:30:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   30 |    assert(v < forb.size());
      |           ~~^~~~~~~~~~~~~
race.cpp: In lambda function:
race.cpp:78:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   78 |   assert(curnode < adj.size());
      |          ~~~~~~~~^~~~~~~~~~~~
race.cpp:81:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   81 |    assert(v < forb.size());
      |           ~~^~~~~~~~~~~~~

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