Submission #1052485

#	Time	Username	Problem	Language	Result	Execution time	Memory
1052485		epicci23	Stations (IOI20_stations)	C++17	100 / 100	543 ms	1296 KiB

stations

#include "bits/stdc++.h"
#include "stations.h"
//#define int long long
#define all(v) v.begin() , v.end()
#define sz(a) (int)a.size()
using namespace std;

const int N = 1005;
vector<int> v[N];
int tin[N],tout[N],col[N],ti=0;
void dfs(int c,int p,int d){
  tin[c]=++ti;
  for(int x:v[c]){
  	if(x==p) continue;
  	dfs(x,c,d^1);
  	tout[c]=max(tout[c],tout[x]);
  }
  tout[c]=++ti;	
  if(d) col[c]=tin[c];
  else col[c]=tout[c];
}

vector<int> label(int n, int k, vector<int> u, vector<int> g){
	ti=0;
	for(int i=0;i<n;i++) v[i].clear();
	vector<int> labels(n);
	for(int i=0;i<n-1;i++){
		int a=u[i],b=g[i];
		v[a].push_back(b);
		v[b].push_back(a);
	}
	dfs(0,0,0);
	map<int,int> mp;
	for(int i=0;i<n;i++) mp[col[i]]=1;
	int p=0;
  for(auto x:mp) mp[x.first]=++p;
	for(int i=0;i<n;i++) labels[i]=mp[col[i]];
	return labels;
}

int find_next_station(int s, int t, vector<int> c){
	sort(all(c));
	int n=sz(c);
	if(n==1) return c[0];
	if(s<c[0]){
       int out=c[n-2];
       if(!(t>=s && t<=out)) return c[n-1];
       int in=s;
       for(int i=0;i<n-1;i++){
         if(t>=in && t<=c[i]) return c[i];
         in=c[i];
       }
       return c[n-1];
	}
	int in=c[1];
	if(!(t>=in && t<=s)) return c[0];
	int out=s;
	for(int i=n-1;i>0;i--){
    if(t>=c[i] && t<=out) return c[i];
    out=c[i];
	}
	return 2323232323;
}

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