Submission #1051553

#	Time	Username	Problem	Language	Result	Execution time	Memory
1051553		Huseyn123	Stations (IOI20_stations)	C++17	100 / 100	537 ms	1188 KiB

stations

#include <bits/stdc++.h> 
#define MAX 1001
#define pb push_back
#include "stations.h"
#include <vector>
using namespace std;
int col[MAX],in[MAX],out[MAX],cnt=-1;
vector<vector<int>> g;
void dfs(int v,int prev){
	cnt+=col[v]%2;
	in[v]=cnt;
	for(auto x:g[v]){
		if(x==prev){
			continue;
		}
		col[x]=1-col[v];
		dfs(x,v);
	}
	cnt+=1-col[v]%2;
	out[v]=cnt;
}
vector<int> label(int n, int k, vector<int> u, vector<int> v) {
	cnt=-1;
	g.clear(); 
	g.resize(n);
	for(int i=0;i<n-1;i++){
		g[u[i]].pb(v[i]); 
		g[v[i]].pb(u[i]);
	}
	vector<int> labels(n);
	col[0]=1;
	dfs(0,-1);
	for(int i=0;i<n;i++){
		if(col[i]){
			labels[i]=in[i];
		}
		else{
			labels[i]=out[i];
		}
	}
	return labels;
}

int find_next_station(int s, int t, vector<int> c) {
	int tp=0;
	int sz=(int)c.size();
	for(auto x:c){
		if(x>s){
			tp=1;
		}
	}
	if(tp==0){
		for(int i=sz-1;i>0;i--){
			int num=s-1;
			if(i!=sz-1){
				num=c[i+1]-1;
			}
			if(t>=c[i] && t<=num){
				return c[i];
			}
		}
		return c[0];
	}
	else{
		for(int i=0;i<sz-1;i++){
			int num=s;
			if(i){
				num=c[i-1];
			}
			if(t>=num && t<=c[i]){
				return c[i];
			}
		}
		return c[sz-1];
	}
}

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