Submission #1073932

#	Time	Username	Problem	Language	Result	Execution time	Memory
1073932		LCJLY	Stations (IOI20_stations)	C++14	100 / 100	663 ms	1184 KiB

stations

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

#define show(x,y) cout << y << " " << #x << endl;
#define show2(x,y,i,j) cout << y << " " << #x << "  " << j << " " << #i << endl;
#define show3(x,y,i,j,p,q) cout << y << " " << #x << "  " << j << " " << #i << "  " << q << " " << #p << endl;
#define show4(x,y) for(auto it:y) cout << it << " "; cout << #x << endl;
typedef pair<int,int>pii; 

vector<int>adj[1005];
bool visited[1005];
int d[1005];
vector<int>ans;
int ptr=0;

void dfs(int index, int par){
	if(d[index]%2==0) ans[index]=ptr++;	
	for(auto it:adj[index]){
		if(it==par) continue;
		d[it]=d[index]+1;
		dfs(it,index);
	}	
	if(d[index]%2==1) ans[index]=ptr++;
}

vector<int>label(int n, int k, vector<int>u, vector<int>v) {
	for(int x=0;x<=n;x++){
		adj[x].clear();
		visited[x]=0;
		d[x]=0;
	}
	ans.clear();
	ans=vector<int>(n,0);
	ptr=0;
	for(int x=0;x<n-1;x++){
		adj[u[x]].push_back(v[x]);
		adj[v[x]].push_back(u[x]);
	}
	
	dfs(0,-1);
	//show4(ans,ans);
	return ans;
}

int find_next_station(int s, int t, vector<int> c) {
	int maxi=0;
	for(auto it:c) maxi=max(maxi,it);
	if(s>maxi){
		vector<int>v;
		for(auto it:c) v.push_back(it);
		//s is out
		sort(v.begin(),v.end());
		int sz=v.size();
		v.push_back(s);
		for(int x=1;x<sz;x++){
			int l=v[x];
			int r=v[x+1]-1;
			if(l<=t&&r>=t){
				return v[x];
			}
		}
		return v[0];
	} 
	else{
		//s is in
		vector<int>v;
		for(auto it:c) v.push_back(it);
		v.push_back(s-1);
		sort(v.begin(),v.end());
		int sz=v.size();
		for(int x=1;x<sz-1;x++){
			int l=v[x-1]+1;
			int r=v[x];
			if(l<=t&&r>=t){
				return v[x];
			}
		}
		return c.back();
	}
	
}

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