Submission #1054578

#	Time	Username	Problem	Language	Result	Execution time	Memory
1054578		pcc	Stations (IOI20_stations)	C++17	100 / 100	564 ms	1384 KiB

stations

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

const int mxn = 1010;
vector<int> tree[mxn];
int dfn[mxn],dep[mxn];
int N;
int ptr = 0;

void init(){
	for(auto &i:tree)i.clear();
	ptr = 0;
	memset(dfn,-1,sizeof(dfn));
	memset(dep,0,sizeof(dep));
}

void dfs(int now,int par){
	if(dep[now]%2 == 0)dfn[now] = ptr++;
	for(auto nxt:tree[now]){
		if(nxt == par)continue;
		dep[nxt] = dep[now]+1;
		dfs(nxt,now);
	}
	if(dep[now]%2 == 1)dfn[now] = ptr++;
	return;
}

std::vector<int> label(int n, int k, std::vector<int> u, std::vector<int> v) {
	init();
	N = n;
	for(int i = 0;i<N-1;i++){
		int a = u[i],b = v[i];
		tree[a].push_back(b);
		tree[b].push_back(a);
	}
	dfs(0,0);
	vector<int> re(N,-1);
	for(int i = 0;i<N;i++)re[i] = dfn[i];
	return re;
}

int find_next_station(int s, int t, std::vector<int> c) {
	set<int> st;
	for(auto &i:c)st.insert(i);
	sort(c.begin(),c.end());
	if(st.find(t) != st.end())return t;
	int par = -1;
	int dir = -1;//if dir = 0:s is in; dir = 1:s is out
	if(s){
		if(c[0]>s){
			par = c.back();
			c.pop_back();
			c.insert(c.begin(),s);
			dir = 0;
		}
		else{
			par = c[0];
			c.erase(c.begin(),c.begin()+1);
			c.push_back(s);
			dir = 1;
		}
	}
	else{
		c.insert(c.begin(),s);
		dir = 0;
	}
	for(int i = 1;i<c.size();i++){
		if(c[i]>=t&&c[i-1]<=t){
			if(dir == 0)return c[i];
			else return c[i-1];
		}
	}
	return par;
}

Compilation message (stderr)

stations.cpp: In function 'int find_next_station(int, int, std::vector<int>)':
stations.cpp:69:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   69 |  for(int i = 1;i<c.size();i++){
      |                ~^~~~~~~~~

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