제출 #431999

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
431999		gonengazit	기지국 (IOI20_stations)	C++14	73.36 / 100	864 ms	792 KiB

stations

#include "stations.h"
#include <vector>
#include <bits/stdc++.h>
using namespace std;
#define ii pair<int,int>
#define x first
#define y second
vector<int> labels;
vector<vector<int>> g;
int tme;
void dfs1(int i,int f=0,int t=0){
	int tin=++tme;
	for(auto u:g[i]){
		if(u!=f){
			dfs1(u,i,(t+1)%2);
		}
	}
	int tout=++tme;
	if(t==0){
		labels[i]=tin*2;
	}
	else{
		labels[i]=tout*2+1;
	}
}

// void dfs1(int i, int f=0){
// 	int tin=++tme;
// 	for(auto u:g[i]){
// 		if(u!=f){
// 			dfs1(u,i);
// 		}
// 	}
// 	int tout=tme;
// 	labels[i]=tin*1000+tout;
// }
std::vector<int> label(int n, int k, std::vector<int> u, std::vector<int> v) {
	tme=-1;
	labels.assign(n,-1);
	g.assign(n,vector<int>());
	for(int i=0; i<n-1; i++){
		g[u[i]].push_back(v[i]);
		g[v[i]].push_back(u[i]);
	}

	dfs1(0);
	return labels;
}

int find_next_station(int s, int t, std::vector<int> c) {
	
	int r=s%2;
	s/=2;
	vector<pair<ii,int>> cld;
	int f=-1;
	if(r==0){
		int prev=s;
		for(auto i:c){
			int k=i/2;
			cld.emplace_back(ii(prev+1,k),i);
			prev=k;
		}
		if(s!=0){
			f=cld.back().y;
			cld.pop_back();
		}
	}
	else{
		f=c[0];
		for(int j=1; j<c.size(); j++){
			int i=c[j];
			int k=i/2;
			if(!cld.empty())
				cld.back().x.y=k-1;
			cld.emplace_back(ii(k,-1),i);
		}
		if(!cld.empty()){
			cld.back().x.y=s;
		}
	}

	t/=2;

	for(auto i:cld){
		if(i.x.x<=t&&i.x.y>=t){
			return i.y;
		}
	}
	return f;
}
/*
1
5 100
0 1
1 2
1 3
2 4
3
0 1 2
1 2 2
1 4 2*/

컴파일 시 표준 에러 (stderr) 메시지

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

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