Submission #436410

#	Time	Username	Problem	Language	Result	Execution time	Memory
436410		20160161simone	Stations (IOI20_stations)	C++14	100 / 100	1253 ms	872 KiB

stations

#include "stations.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N=1e3+10;
struct edge{
	ll to,nxt;
}ln[N*2];
ll idx[N],topln;
void add_edge(ll u,ll v){
	ln[++topln]=(edge){v,idx[u]},idx[u]=topln;
	ln[++topln]=(edge){u,idx[v]},idx[v]=topln;
}
ll dep[N],dfn[N],siz[N];
void dfs0(ll x,ll fa){
	siz[x]=1;
	for(ll i=idx[x];i;i=ln[i].nxt){
		if(ln[i].to==fa) continue;
		dfs0(ln[i].to,x);
		siz[x]+=siz[ln[i].to];
	}
}
void dfs(ll x,ll fa,ll l,ll r){
	if(dep[x]%2==0) dfn[x]=l; 
	else dfn[x]=r;
	ll t=dfn[x];
	// printf(":: %lld %lld %lld\n",x,l,r);
	for(ll i=idx[x];i;i=ln[i].nxt){
		if(ln[i].to==fa) continue;
		dep[ln[i].to]=dep[x]+1;
		if(dep[x]%2==0){
			dfs(ln[i].to,x,t+1,t+siz[ln[i].to]);
			t+=siz[ln[i].to];
		}
		else{
			dfs(ln[i].to,x,t-siz[ln[i].to],t-1);
			t-=siz[ln[i].to];
		}
	}
}
 
vector<int> label(int n, int k, vector<int> u, vector<int> v) {
	memset(dep,0,sizeof(dep));
	memset(dfn,0,sizeof(dfn));
	memset(idx,0,sizeof(idx));
	topln=0;
	for(ll i=0;i<u.size();i++) add_edge(u[i],v[i]);
	dfs0(0,0);
	dfs(0,0,1,n);
	vector<int> lab;
	for(ll i=0;i<n;i++) lab.push_back(dfn[i]);
	// for(ll i=0;i<n;i++) printf("%lld ",siz[i]);cout<<endl;
	return lab;
}
 
int find_next_station(int s, int t, vector<int> c) {
	for(ll i=0;i<c.size();i++){
		if(t==c[i]) return c[i];
	}
	// for(ll i=0;i<c.size();i++) printf("%lld ",c[i]);cout<<endl;
	if(s<c[0]){
		for(ll i=0;i<c.size()-1;i++){
			if(s<t && t<c[i]) return c[i];
		}
		return c[c.size()-1];
	}
	else{//c[0]<s
		for(ll i=c.size()-1;i>0;i--){
			if(c[i]<t && t<s) return c[i];
		}
		return c[0];
	}
	//printf("%lld %lld\n",s,t);
}

Compilation message (stderr)

stations.cpp: In function 'std::vector<int> label(int, int, std::vector<int>, std::vector<int>)':
stations.cpp:47:14: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   47 |  for(ll i=0;i<u.size();i++) add_edge(u[i],v[i]);
      |             ~^~~~~~~~~
stations.cpp: In function 'int find_next_station(int, int, std::vector<int>)':
stations.cpp:57:14: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   57 |  for(ll i=0;i<c.size();i++){
      |             ~^~~~~~~~~
stations.cpp:62:15: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   62 |   for(ll i=0;i<c.size()-1;i++){
      |              ~^~~~~~~~~~~

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