Submission #617068

#	Time	Username	Problem	Language	Result	Execution time	Memory
617068		chirathnirodha	Stations (IOI20_stations)	C++17	0 / 100	788 ms	800 KiB

stations

#include "stations.h"
#include<bits/stdc++.h>
using namespace std;
#define PB push_back
#define MP make_pair
#define F first
#define S second 
vector<pair<int,int>> lab;
int in[1000],out[1000];
vector<int> ed[1000];
int cur;
void dfs(int x,int dep){
	in[x]=cur;cur++;
	for(int i=0;i<ed[x].size();i++){
		int y=ed[x][i];
		if(in[y]!=-1)continue;
		dfs(y,dep+1);
	}
	out[x]=cur;cur++;
	if(dep%2==0)lab.PB(MP(in[x],x));
	else lab.PB(MP(out[x],x));
}
vector<int> label(int n, int k, vector<int> u, vector<int> v) {
	memset(in,-1,sizeof(in));
	memset(out,-1,sizeof(out));
	lab.clear();
	for(int i=0;i<n;i++)ed[i].clear();
	for(int i=0;i<n-1;i++){
		ed[u[i]].PB(v[i]);
		ed[v[i]].PB(u[i]);
	}
	cur=0;
	dfs(0,0);
	sort(lab.begin(),lab.end());
	vector<int> labels(n);
	for(int i=0;i<n;i++){
		labels[lab[i].S]=i;
	}
	return labels;
}

int find_next_station(int s, int t, vector<int> c) {
	sort(c.begin(),c.end());
	if(s<c[0]){
		int par=c.back();
		if(s!=0)c.pop_back();
		for(int i=0;i<c.size();i++){
			if(t<=c[i])return c[i];
		}
		return par;
	}
	else{
		for(int i=c.size();i>0;i--){
			if(t>=c[i])return c[i];
		}
		return c[0];
	}
	return c[0];
}

Compilation message (stderr)

stations.cpp: In function 'void dfs(int, int)':
stations.cpp:14:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   14 |  for(int i=0;i<ed[x].size();i++){
      |              ~^~~~~~~~~~~~~
stations.cpp: In function 'int find_next_station(int, int, std::vector<int>)':
stations.cpp:47:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   47 |   for(int i=0;i<c.size();i++){
      |               ~^~~~~~~~~

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