Submission #923660

#	Time	Username	Problem	Language	Result	Execution time	Memory
923660		oblantis	Stations (IOI20_stations)	C++17	0 / 100	545 ms	1616 KiB

stations

#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#pragma GCC optimize("O3,unroll-loops")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define all(v) v.begin(), v.end()
#define pb push_back
#define ss second
#define ff first
#define vt vector
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef pair<int, int> pii;
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
const int inf = 1e9;
const int mod = 1e9+7;
const int maxn = 1e4 + 1;
//#include "stations.h"
bool wt[maxn];
vt<int> g[maxn];
vt<pii> asgn;
int in[maxn], out[maxn], cnt;
void dfs(int i, int p){
	in[i] = cnt++;
	for(auto j : g[i]){
		if(j == p)continue;
		wt[j] = wt[i] ^ 1;
		dfs(j, i);
	}
	out[i] = cnt++;
	if(wt[i])asgn.pb({out[i], i});
	else asgn.pb({in[i], i});
}
vector<int> label(int n, int k, vector<int> u, vector<int> v) {
	vector<int> labels(n);
	cnt = 0;
	asgn.clear();
	for(int i = 0; i <= n; i++)g[i].clear();
	for(int i = 0; i < n - 1; i++){
		g[u[i]].pb(v[i]), g[v[i]].pb(u[i]);
	}
	wt[0] = 0;
	dfs(0, -1);
	cnt = 0;
	sort(all(asgn));
	for(auto i : asgn){
		labels[i.ss] = cnt++;
	}
	return labels;
}

int find_next_station(int s, int t, vector<int> c) {
	sort(all(c));
	if(s < c[0]){
		for(auto i : c){
			if(s <= t && t <= i)return i;
		}
		return c.back();
	}
	else {
		reverse(all(c));
		for(auto i : c){
			if(s >= t && t >= i)return i;
		}
		return c[0];
	}
}

//void solve() {
	
//}

//int main() {
	//ios_base::sync_with_stdio(0);
	//cin.tie(0);
	//int times = 1;
	////cin >> times;
	//for(int i = 1; i <= times; i++) {
		//solve();
	//}
	//return 0;
//}
//#include "stations.h"
//#include <cstdio>
//#include <cassert>
//#include <map>
//#include <vector>
//#include <algorithm>

//static int max_label = 0;
//static int r, n, k, q;
//static std::vector<int> u, v, labels, answers;
//static std::map<int, int> reverse_labels;
//static std::vector<std::vector<int>> adjlist;
//static int s, t, w;
//static std::vector<int> c;

//int main() {
	//assert(scanf("%d", &r) == 1);
	//for (int tc = 0; tc < r; tc++) {
		//assert(scanf("%d%d", &n, &k) == 2);
		//u.resize(n - 1);
		//v.resize(n - 1);
		//adjlist.clear();
		//adjlist.resize(n);
		//for (int i = 0; i < n - 1; i++) {
			//assert(scanf("%d%d", &u[i], &v[i]) == 2);
			//adjlist[u[i]].push_back(v[i]);
			//adjlist[v[i]].push_back(u[i]);
		//}
		//labels = label(n, k, u, v);
		//if ((int)labels.size() != n) {
			//printf("Number of labels not equal to %d\n", n);
			//exit(0);
		//}
		//reverse_labels.clear();
		//for (int i = 0; i < n; i++) {
			//if (labels[i] < 0 || labels[i] > k) {
				//printf("Label not in range 0 to %d\n", k);
				//exit(0);
			//}
			//if (reverse_labels.find(labels[i]) != reverse_labels.end()) {
				//printf("Labels not unique\n");
				//exit(0);
			//}
			//reverse_labels[labels[i]] = i;
			//if (labels[i] > max_label) {
				//max_label = labels[i];
			//}
		//}
		//assert(scanf("%d", &q) == 1);
		//for (int i = 0; i < q; i++) {
			//assert(scanf("%d%d%d", &s, &t, &w) == 3);
			//c.clear();
			//for (int v : adjlist[s]) {
				//c.push_back(labels[v]);
			//}
			//std::sort(c.begin(), c.end());
			//int answer = find_next_station(labels[s], labels[t], c);
			//if (!std::binary_search(c.begin(), c.end(), answer)) {
				//printf("Label %d returned by find_next_station not found in c\n", answer);
				//exit(0);
			//}
			//answers.push_back(reverse_labels[answer]);
		//}
	//}
	//printf("%d\n", max_label);
	//for (int index : answers) {
		//printf("%d\n", index);
	//}
	//exit(0);
//}

• Subtask 1: 0 / 5
• Subtask 2: 0 / 8
• Subtask 3: 0 / 16
• Subtask 4: 0 / 10
• Subtask 5: 0 / 61