Submission #1234481

#	Time	Username	Problem	Language	Result	Execution time	Memory
1234481		pcp	Stations (IOI20_stations)	C++20	100 / 100	303 ms	572 KiB

stations

#include <vector>
#include <stack>
#include <iostream>
#include <algorithm>
using namespace std;

void dfs(vector<vector<int>> &connections, int node, int depth, int &count, vector<int> &cons){

	if (cons[node]!=-1)return;
	++depth;

	if (depth%2!=0){++count;cons[node]=count;}
	else cons[node]=-2;



	for (int it : connections[node]){
		dfs(connections,it,depth,count,cons);
	}

	if (depth%2==0){++count;cons[node]=count;}

}

std::vector<int> label(int n, int k, std::vector<int> u, std::vector<int> v) {
	std::vector<vector<int>> connections(n);



	for (int i = 0; i < n-1; i++) {
		connections[u[i]].push_back(v[i]);
		connections[v[i]].push_back(u[i]);
	}



	vector<int> cons(n,-1);



	int count = -1;
	dfs(connections,0,-1,count,cons);

	return cons;
}

int find_next_station(int s, int t, std::vector<int> c) {
	int csize=c.size();
	if (s<c[0]){

            
            int bf = s;
            
            for (int i = 0; i < csize-1;++i){
                if (t > bf && t<=c[i])return c[i];
                bf=c[i];
            
            }
            return c[csize-1];
    
	}else{
            reverse(c.begin(),c.end());
            int bf = s;
            
            for (int i = 0; i < csize-1;++i){
                if (t >=c[i] && t<bf)return c[i];
                bf=c[i];
            
            }
            return c[csize-1];
    
	}
	
	
}

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