Submission #565128

#	Time	Username	Problem	Language	Result	Execution time	Memory
565128		luka1234	Stations (IOI20_stations)	C++14	0 / 100	3061 ms	2097156 KiB

stations

#include "stations.h"
#include<bits/stdc++.h>
#include <vector>
using namespace std;
vector<int> g[1001];
int tin=0;
int lab[1001];
map<int,int> mp;
void dfs(int v,int e,bool b){
	tin++;
	if(b==0)
	   lab[v]=tin;
	for(int i:g[v]){
		if(i!=e){
			dfs(i,v,!b);
		}
	}
	tin++;
	if(b==1)
	   lab[v]=tin;
}
std::vector<int> label(int n, int k, std::vector<int> u, std::vector<int> v) {
	std::vector<int> labels(n);
	vector<int> vec;
	for(int i=0;i<n;i++)
	    g[i].clear();
	for(int i=0;i<n;i++){
		g[v[i]].push_back(u[i]);
		g[u[i]].push_back(v[i]);
	}
	dfs(0,-1,0);
	for(int k=0;k<n;k++){
		vec.push_back(lab[k]);
	}
	sort(vec.begin(),vec.end());
	for(int k=0;k<vec.size();k++){
		mp[vec[k]]=k;
	}
	for(int k=0;k<n;k++){
		lab[k]=mp[lab[k]];
		labels[k]=lab[k];
	}
	return labels;
}

int find_next_station(int s, int t, std::vector<int> c){
	sort(c.begin(),c.end());
	if(c.size()==1)
	   return c[0];
	if(s>c[0]){
		int mn=c[1];
		int mx=s;
		if(!(t>=mn&&t<=mx))
		   return c[0];
		else{
			for(int k=c.size()-1;k>0;k--){
				if(t>=c[k]&&t<=mx)
				   return c[k];
			}
		}
	}
	else{
		int mn=s;
		int mx=c[c.size()-2];
		if(!(t>=mn&&t<=mx))
		   return c[c.size()-1];
		else{
			for(int k=0;k<c.size()-1;k++){
				if(t>=s&&t<=c[k])
				   return c[k];
			}
		}
	}
}

Compilation message (stderr)

stations.cpp: In function 'std::vector<int> label(int, int, std::vector<int>, std::vector<int>)':
stations.cpp:36:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   36 |  for(int k=0;k<vec.size();k++){
      |              ~^~~~~~~~~~~
stations.cpp: In function 'int find_next_station(int, int, std::vector<int>)':
stations.cpp:68:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   68 |    for(int k=0;k<c.size()-1;k++){
      |                ~^~~~~~~~~~~
stations.cpp:74:1: warning: control reaches end of non-void function [-Wreturn-type]
   74 | }
      | ^

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