Submission #435991

#	Time	Username	Problem	Language	Result	Execution time	Memory
435991		20160161simone	Stations (IOI20_stations)	C++14	0 / 100	1297 ms	668 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],L,R;
void dfs(ll x,ll fa){
	if(dep[x]%2==0) dfn[x]=R,R--; 
	else dfn[x]=L,L++;
//	printf("%lld %lld\n",x,dfn[x]);
	for(ll i=idx[x];i;i=ln[i].nxt){
		if(ln[i].to==fa) continue;
		dep[ln[i].to]=dep[x]+1;
		dfs(ln[i].to,x);
	}
}

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;
	L=1,R=n;
	for(ll i=0;i<u.size();i++) add_edge(u[i],v[i]);
	dfs(0,0);
	vector<int> lab;
	for(ll i=0;i<n;i++) lab.push_back(dfn[i]);
	return lab;
}

int find_next_station(int s, int t, vector<int> c) {
	if(s<c[0]){
		if(t<s) return c[c.size()-1];
		for(ll i=0;i<c.size()-1;i++){
			if(t<c[i]) return c[i];
		}
	}
	else{//c[0]<s
		if(s<t) return c[0];
		for(ll i=1;i<c.size();i++){
			if(c[i]<t) return c[i];
		}
	}
}

Compilation message (stderr)

stations.cpp: In function 'std::vector<int> label(int, int, std::vector<int>, std::vector<int>)':
stations.cpp:32: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]
   32 |  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:42: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]
   42 |   for(ll i=0;i<c.size()-1;i++){
      |              ~^~~~~~~~~~~
stations.cpp:48: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]
   48 |   for(ll i=1;i<c.size();i++){
      |              ~^~~~~~~~~
stations.cpp:52:1: warning: control reaches end of non-void function [-Wreturn-type]
   52 | }
      | ^

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