Submission #376434

#	Time	Username	Problem	Language	Result	Execution time	Memory
376434		mosiashvililuka	Stations (IOI20_stations)	C++14	100 / 100	1007 ms	1284 KiB

stations

#include "stations.h"
#include <vector>
#include<bits/stdc++.h>
using namespace std;
int a,b,c,d,e,i,j,ii,jj,zx,xc,tim,lf[1009],rg[1009],dep[1009],pi;
vector <int> v[1009];
pair <int, int> p[1009];
void dfs(int q, int w){
	if(w!=-1) dep[q]=dep[w]+1;
	tim++;
	lf[q]=tim;
	for(vector <int>::iterator it=v[q].begin(); it!=v[q].end(); it++){
		if((*it)==w) continue;
		dfs((*it),q);
	}
	tim++;
	rg[q]=tim;
	if(dep[q]%2==0){
		pi++;
		p[pi].first=lf[q];
		p[pi].second=q;
	}else{
		pi++;
		p[pi].first=rg[q];
		p[pi].second=q;
	}
}
vector<int> label(int n, int kk, vector<int> U, vector<int> V) {
	vector<int> labels(n);
	pi=0;tim=0;
	for(i=0; i<=n; i++){
		v[i].clear();
		dep[i]=0;
		lf[i]=rg[i]=0;
	}
	for(i=0; i<n-1; i++){
		v[U[i]].push_back(V[i]);
		v[V[i]].push_back(U[i]);
	}
	//cout<<pi<<" ra "<<endl;
	dfs(0,-1);
	sort(p+1,p+pi+1);
	//cout<<pi<<" kd "<<endl;
	for(i=1; i<=pi; i++){
		//cout<<p[i].first<<" "<<p[i].second<<endl;
		labels[p[i].second]=i-1;
	}
	return labels;
}

int find_next_station(int s, int t, std::vector<int> C) {
	for(i=0; i<C.size(); i++){
		if(C[i]==t){
			return t;
		}
	}
	e=0;
	for(i=0; i<C.size(); i++){
		if(C[i]>s){
			e=1;
			break;
		}
	}
	if(e==0){
		sort(C.begin(),C.end());
		for(i=1; i<C.size(); i++){
			if(t>=C[i-1]&&t<C[i]){
				return C[i-1];
			}
		}
		if(t>=C[C.size()-1]&&t<s){
			return C[C.size()-1];
		}
		return C[0];
	}else{
		sort(C.begin(),C.end());
		if(s==0){
			for(i=0; i<C.size(); i++){
				if(t<=C[i]){
					return C[i];
				}
			}
		}else{
			if(t<s){
				return C[C.size()-1];
			}
			for(i=0; i<C.size(); i++){
				if(i+1>=C.size()) break;
				if(t<=C[i]){
					return C[i];
				}
			}
			return C[C.size()-1];
		}
	}
}

Compilation message (stderr)

stations.cpp: In function 'int find_next_station(int, int, std::vector<int>)':
stations.cpp:52:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   52 |  for(i=0; i<C.size(); i++){
      |           ~^~~~~~~~~
stations.cpp:58:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   58 |  for(i=0; i<C.size(); i++){
      |           ~^~~~~~~~~
stations.cpp:66:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   66 |   for(i=1; i<C.size(); i++){
      |            ~^~~~~~~~~
stations.cpp:78:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   78 |    for(i=0; i<C.size(); i++){
      |             ~^~~~~~~~~
stations.cpp:87:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   87 |    for(i=0; i<C.size(); i++){
      |             ~^~~~~~~~~
stations.cpp:88:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   88 |     if(i+1>=C.size()) break;
      |        ~~~^~~~~~~~~~
stations.cpp:96:1: warning: control reaches end of non-void function [-Wreturn-type]
   96 | }
      | ^

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