Submission #900142

#	Time	Username	Problem	Language	Result	Execution time	Memory
900142		Malix	기지국 (IOI20_stations)	C++14	100 / 100	527 ms	1628 KiB

stations

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

typedef long long ll;
typedef vector<int> vi;
typedef pair<int,int> pi;

#define REP(i,a,b) for(int i=a;i<b;i++)
#define F first
#define S second
#define PB push_back
#define MP make_pair

void doLess(int a,vi &labels,vi &s,vector<vi> &paths,vi &parent);
void doMore(int a,vi &labels,vi &s,vector<vi> &paths,vi &parent);

int dp(int a,vi &parent,vector<vi> &paths,vi &s){
	if(paths[a].size()==1)return 1;
	for(auto u:paths[a]){
		if(u==parent[a])continue;
		parent[u]=a;
		s[a]+=dp(u,parent,paths,s);
	}
	return s[a];
}

void doLess(int a,vi &labels,vi &s,vector<vi> &paths,vi &parent){
	int d=labels[a];
	for(auto u:paths[a]){
		if(u==parent[a])continue;
		labels[u]=d-s[u];
		doMore(u,labels,s,paths,parent);
		d=labels[u];
	}
}

void doMore(int a,vi &labels,vi &s,vector<vi> &paths,vi &parent){
	int d=labels[a];
	for(auto u:paths[a]){
		if(u==parent[a])continue;
		labels[u]=d+s[u];
		doLess(u,labels,s,paths,parent);
		d=labels[u];
	}
	
}

std::vector<int> label(int n, int k, std::vector<int> u, std::vector<int> v) {
	
	std::vector<int> labels(n);
	vector<vi> paths(n);
	REP(i,0,n-1){
		paths[u[i]].PB(v[i]);
		paths[v[i]].PB(u[i]);
	}
	vi parent(n);
	parent[0]=0;
	vi s(n,1);
	for(auto u:paths[0]){
		parent[u]=0;
		s[0]+=dp(u,parent,paths,s);
	}
	labels[0]=0;
	int d=0;
	for(auto u:paths[0]){
		labels[u]=d+s[u];
		doLess(u,labels,s,paths,parent);
		d=labels[u];
	}
	//REP(i,0,n)cout<<labels[i]<<" ";
	return labels;
}

int find_next_station(int s, int t, std::vector<int> c) {
	if(c.size()==1)return c[0];
	if(s==0){
		auto it=lower_bound(c.begin(),c.end(),t);
		return *it;
	}
	if(c[0]>s){
		int g=c.back();
		c.pop_back();
		if(t>c.back()||t<s)return g;
		auto it=lower_bound(c.begin(),c.end(),t);
		return *it;
	}
	if(t<c[1]||t>s)return c[0];
	auto it=lower_bound(c.begin(),c.end(),t);
	if(it==c.end())return c.back();
	if(*it==t)return *it;
	it--;
	return *it;
	return c[0];
}

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