Submission #923647

#	Time	Username	Problem	Language	Result	Execution time	Memory
923647		oblantis	Stations (IOI20_stations)	C++17	0 / 100	1730 ms	2097152 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"
#include <vector>
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);
	for(int i = 0; i < n - 1; i++){
		g[u[i]].pb(v[i]), g[v[i]].pb(u[i]);
	}
	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;
//}

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