Submission #620785

#	Time	Username	Problem	Language	Result	Execution time	Memory
620785		KLPP	Stations (IOI20_stations)	C++14	0 / 100	800 ms	5540 KiB

stations

#include "stations.h"
#include <vector>
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=a;i<b;i++)
#define trav(a,v) for(auto a:v)
typedef long long int lld;
vector<int> nei[100000];
int L[100000];
int R[100000];
int cnt;
bool visited[100000];
bool parity[1000000];
void DFS(int node){
	visited[node]=true;
	L[node]=cnt;
	cnt++;
	trav(a,nei[node]){
		if(!visited[a]){
			parity[a]=1^parity[node];
			DFS(a);
		}
	}
	R[node]=cnt-1;
}
std::vector<int> label(int n, int k, std::vector<int> u, std::vector<int> v) {
	rep(i,0,n)nei[i].clear();
	rep(i,0,(int)u.size()){
		nei[u[i]].push_back(v[i]);
		nei[v[i]].push_back(u[i]);
	}
	cnt=0;
	
	rep(i,0,n)visited[i]=false;
	parity[0]=false;
	DFS(0);
	vector<pair<pair<int,int>,pair<int,int> > >V(n);
	rep(i,0,n){
		V[i]={{(parity[i] ? R[i] : L[i]),parity[i]},{-L[i],i}};
	}
	sort(V.begin(),V.end());
	/*rep(i,0,n){
		cout<<R[V[i].second.second]<<endl;
		cout<<V[i].first.first<<" "<<V[i].first.second<<" "<<V[i].second.first<<" "<<V[i].second.second<<endl;
	}*/
	vector<int> answer(n);
	rep(i,0,n)answer[V[i].second.second]=i;

	//rep(i,0,n)cout<<answer[i]<<endl;
	return answer;
}

int find_next_station(int s, int t, std::vector<int> c) {
	sort(c.begin(),c.end());
	if(c[c.size()-1]<s){
		//parity=R
		int L=c[1];
		int R=s;
		if(t<L || R<t){
			return c[0];
		}
		int best=1000000;
		trav(a,c){
			if(a>=t)best=min(best,a);
		}
		return best;
	}
	//parity=L
	reverse(c.begin(),c.end());
	int L=s;
	int R=c[1];
	if(t<L || R<t)return c[0];
	int best=-1;
	trav(a,c){
		if(a<=t)best=max(best,a);
	}
	return best;
}

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