Submission #714453

#	Time	Username	Problem	Language	Result	Execution time	Memory
714453		kaxzert	Race (IOI11_race)	C++17	0 / 100	13 ms	17876 KiB

race

#include<bits/stdc++.h>

using namespace std;

#define fto(i, a, b) for(int i = a; i <= b; ++i)
#define fdto(i, a, b) for(int i = a; i >= b; --i)
#define bugarr(a, i, j) cout << #a << "{" << i << "..." << j << "}:"; fto(k, i, j-1) cout << a[k] << ", "; cout << a[j] << endl;
#define ll long long
#define db double
#define ldb long double
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
#define eb emplace_back
#define vt vector
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define trav(i, a) for(auto &i : a)
#define sz(a) (int)a.size()
#define pi(a, b) pair<a, b>
#define fast ios::sync_with_stdio(false); cin.tie(0)

void setIO(string s) {
    if (sz(s) != 0) {
        freopen((s+".inp").c_str(),"r",stdin);
        //freopen((s+".out").c_str(),"w",stdout);
    }
}

void setIOusaco(string s) {
    if (sz(s) != 0) {
        freopen((s+".in").c_str(),"r",stdin);
        freopen((s+".out").c_str(),"w",stdout);
    }
}

template<typename T, typename V>
bool ckmin(T &a, V b) {return (b < a)? a = b, true : false;}
template<typename T, typename V>
bool ckmax(T &a, V b) {return (b > a)? a = b, true : false;}

void print(int x) {cout << x;}
void print(long long x) {cout << x;}
void print(unsigned x) {cout << x;}
void print(unsigned long long x) {cout << x;}
void print(double x) {cout << fixed << x;}
void print(long double x) {cout << fixed << x;}
void print(char x) {cout << "'" << x << "'";}
void print(string x) {cout << '"' << x << '"';}
void print(bool x) {cout << (x ? "true" : "false");}

template<typename T, typename V>
void print(const pair<T, V> &x) {cout << '{'; print(x.ff); cout << ", "; print(x.ss); cout << '}';}
template<typename T>
void print(const T &x) {int f = 0; cout << '{'; for (auto &i: x) cout << (f++ ? ", " : ""), print(i); cout << "}";}
void _print() {cout << "]" << endl;}
template <typename T, typename... V>
void _print(T t, V... v) {print(t); if (sizeof...(v)) cout << ", "; _print(v...);}

#define bug(x...) cout << "[" << #x << "] = ["; _print(x)

const int MAXN = 200007;
const int MAXK = 1000007;
int n, k, ans, min_depth[MAXK], s[MAXN], r[MAXN];
vt<pair<int, int> > ke[MAXN], paths;

int dfs(int u, int p = -1) {
	s[u] = 1;
	trav(c, ke[u]) {
		int v = c.ff;
		if (v == p || r[v]) continue;
		s[u] += dfs(v, u);
	}
	return s[u];
}

int find_centroid(int u, int ms, int p = -1) {
	trav(c, ke[u]) {
		int v = c.ff;
		if (v == p || r[v] || s[v]*2 < ms) continue;
		return find_centroid(v, ms, u);
	}
	return u;
}

void dfs2(int u, int p = -1, int depth = 0, int len = 0) {
	if (p != -1) paths.pb(mp(len, depth));
	trav(c, ke[u]) {
		int v = c.ff;
		int val = c.ss;
		if (v == p || r[v]) continue;
		dfs2(v, u, depth+1, len+val);
	}
}

void centroid(int u) {
	int tree_centroid = find_centroid(u, dfs(u));
	r[tree_centroid] = 1;

	dfs2(tree_centroid);
	
	fto(i, 0, sz(paths)-1) {
		if (paths[i].ss == 1) {
			fto(j, i, sz(paths)-1) { 
				if (k-paths[j].ff >= 0 && k-paths[j].ff <= 1000000) ans = min(ans, min_depth[k-paths[j].ff] + paths[j].ss);
				if (j == sz(paths) || paths[j+1].ss == 1) break;
			}
		}
		
		min_depth[paths[i].ff] = min(min_depth[paths[i].ff], paths[i].ss);
	}

	trav(c, paths) min_depth[c.ff] = (int)1e9;
	paths.clear();

	trav(c, ke[tree_centroid]) {
		int v = c.ff;
		if (!r[v]) centroid(v);
	}
}

int best_path(int n_, int k_, int edges[][2], int weights[]){
	//setIO("race_ioi2011");
    //ios::sync_with_stdio(false); cin.tie(0);
    n = n_;
	k = k_;
	fto(i, 0, n-2) {
		int u = edges[i][0];
		int v = edges[i][1];
		int l = weights[i];
		ke[u].pb(mp(v, l));
		ke[v].pb(mp(u, l));
	}
	
 	ans = (int)1e9;
 	min_depth[0] = 0;
 	fto(i, 1, 1000000) min_depth[i] = (int)1e9;

 	centroid(0);

 	return ((ans == (int)1e9) ? -1 : ans);
}


//int main() {
//	setIO("race_ioi2011");
//    ios::sync_with_stdio(false); cin.tie(0);
//   
//		
//	cin >> n >> k;
//	fto(i, 0, n-2) {
//		int u, v, l;
//		cin >> u >> v >> l;
//		ke[u].pb(mp(v, l));
//		ke[v].pb(mp(u, l));
//	}
//
//	ans = (int)1e9;
//	min_depth[0] = 0;
//	fto(i, 1, 1000000) min_depth[i] = (int)1e9;
//
//	centroid(0);
//
//	cout << ((ans == (int)1e9) ? -1 : ans) << '\n';
//   
//    return 0;
//}

Compilation message (stderr)

race.cpp: In function 'void setIO(std::string)':
race.cpp:26:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   26 |         freopen((s+".inp").c_str(),"r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
race.cpp: In function 'void setIOusaco(std::string)':
race.cpp:33:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   33 |         freopen((s+".in").c_str(),"r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
race.cpp:34:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   34 |         freopen((s+".out").c_str(),"w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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