Submission #304977

#	Time	Username	Problem	Language	Result	Execution time	Memory
304977		arnold518	Stations (IOI20_stations)	C++14	100 / 100	1176 ms	1128 KiB

stations

#include "stations.h"
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

static const int MAXN = 1000;

static int N, K;
static vector<int> adj[MAXN+10];
static int L[MAXN+10], R[MAXN+10], D[MAXN+10];
static int ans[MAXN+10];

static int cnt;

void dfs(int now, int bef, int col)
{
	if(col) cnt++;
	L[now]=cnt;
	D[now]=col;
	for(int nxt : adj[now])
	{
		if(nxt==bef) continue;
		dfs(nxt, now, 1-col);
	}
	if(!col) cnt++;
	R[now]=cnt;
}

vector<int> label(int _N, int _K, vector<int> _U, vector<int> _V)
{
	N=_N;
	for(int i=0; i+1<N; i++)
	{
		int u=_U[i], v=_V[i];
		adj[u].push_back(v);
		adj[v].push_back(u);
	}

	cnt=0;
	dfs(0, 0, 1);

	for(int i=0; i<N; i++)
	{
		if(D[i]) ans[i]=L[i];
		else ans[i]=R[i];
	}

	for(int i=0; i<N; i++) adj[i].clear();

	vector<int> ans2;
	ans2.resize(N);
	for(int i=0; i<N; i++) ans2[i]=ans[i];
	return ans2;
}


int find_next_station(int _S, int _T, vector<int> _C)
{
static int S, T, D;
static vector<int> C;
	S=_S; T=_T; D=_C.size(); C=_C;

	if(D==1) return C[0];
	if(S==0) return *lower_bound(C.begin(), C.end(), T);

	if(C[0]>S)
	{
		int P=C.back(); C.pop_back();
		if(S+1<=T && T<=C.back()) return *lower_bound(C.begin(), C.end(), T);
		else return P;
	}
	else
	{
		int P=C[0]; C.erase(C.begin());
		if(C[0]<=T && T<=S-1) return *(--upper_bound(C.begin(), C.end(), T));
		else return P;
	}
}

Compilation message (stderr)

stations.cpp:11:15: warning: 'K' defined but not used [-Wunused-variable]
   11 | static int N, K;
      |               ^

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