제출 #1241250

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1241250		muhammad-mutahir	기지국 (IOI20_stations)	C++20	0 / 100	309 ms	652 KiB

stations

#include "stations.h"
#include <bits/stdc++.h>

using namespace std;
#define all(l) l.begin(),l.end()
#define pb push_back

// vector<int> labels,vis;
// vector<vector<int>>adj;
// int t = 0;
void dfs(int y,int p,vector<int>&vis,vector<int>&labels,vector<vector<int>>&adj,int &t){
	if(p == 0)
	labels[y] = t;
	t++;
	for(int i:adj[y]){
		if(!vis[i]){
			vis[i] = 1;
			dfs(i,p^1,vis,labels,adj,t);
			t++;
		}
	}
	if(p == 1){
		labels[y] = --t;

	}
}

vector<int> label(int n, int k,vector<int> u, vector<int> v) {
	vector<int> labels,vis;
	vector<vector<int>>adj;
	labels.resize(n,0);
	adj.resize(n+1);
	vis.resize(n+1,0);
	for(int i = 0;i<n-1;i++){
		adj[u[i]].push_back(v[i]);
		adj[v[i]].push_back(u[i]);
	}
	int t = 0;
	vis[0] = 1;
	dfs(0,0,vis,labels,adj,t);
	vector<vector<int>>ord;
	for(int i = 0;i<n;i++)ord.pb({labels[i],i});
	sort(all(ord));
	t = 0;
	for(auto i:ord){
		labels[i[1]] = t;
		t++;
	}
	return labels;
}

int find_next_station(int s, int t, vector<int> c) {
	sort(all(c));
	int n = c.size();
	if(n == 1){
		return c[0];
	}
	if(c[0] > s){

		if(s > t){
			return c.back();
		}
		else{
			for(int i = 0;i<n-1;i++){
				if(c[i] >= t){
					return c[i];
				}
			}
		}
	}
	else{
		if(s < t){
			return c[0];
		}
		else{

			for(int i = n-1;i>0;i--){
				if(c[i] <= t){
					return c[i];
				}
			}
		}
	}
	return c[0];

}


// int main(){
// 	freopen("inp.in","r",stdin);
// 	freopen("out.in","w",stdout);
// 	vector<int>ans = label(9,10,{0,1,1,2,2,4,6,6},{1,2,3,4,5,6,7,8});
// 	for(int i:ans){
// 		cout<<i<<" ";
// 	}
// 	cout<<endl;
// 	cout<<find_next_station(1,2,{5,6})<<endl;


// }

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