Submission #474454

#	Time	Username	Problem	Language	Result	Execution time	Memory
474454		cs71107	Stations (IOI20_stations)	C++14	100 / 100	1297 ms	768 KiB

stations

#include "stations.h"

#include <bits/stdc++.h>

using namespace std;

const int MAXM = 1e3+10;

vector<vector<int> > graph;

int depth[MAXM];
int val[MAXM];

int seq = 0;

void dfs(int here,int p){

	int there;

	if(!(depth[here]&1)){
		val[here] = seq;
		seq++;
	}


	for(int i=0;i<(int)graph[here].size();i++){
		there = graph[here][i];
		if(there==p)continue;
		depth[there] = depth[here]^1;
		dfs(there,here);
	}

	if(depth[here]&1){
		val[here] = seq;
		seq++;
	}

	return;
}


std::vector<int> label(int n, int k, std::vector<int> u, std::vector<int> v) {

	graph = vector<vector<int> > (n);

	for(int i=0;i<n-1;i++){
		graph[u[i]].push_back(v[i]);
		graph[v[i]].push_back(u[i]);
	}

	seq = 0;
	depth[0] = 0;
	dfs(0,-1);

	vector<int> labels(n);

	for(int i=0;i<n;i++){
		labels[i] = val[i];
	}

	return labels;
}

int find_next_station(int s, int t, std::vector<int> c) {
	
	int m = (int)c.size();

	if(m==1)return c[0];

	int idx = -1;
	int pre = 0;
	int nxt = 0;

	if(s<c[0]){
		
		pre = s;

		for(int i=0;i<m-1;i++){
			if(pre+1<=t&&t<=c[i]){
				idx = i;
				break;
			}
			pre = c[i];
		}

		if(idx==-1)idx = m-1;

	}
	else {

		for(int i=1;i<m;i++){
			if(i==m-1)nxt = s;
			else nxt = c[i+1];

			if(c[i]<=t&&t<=nxt-1){
				idx = i;
				break;
			}
		}

		if(idx==-1)idx = 0;
	}
	
	assert(idx!=-1);

	return c[idx];
}

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