제출 #305154

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
305154		ScarletS	기지국 (IOI20_stations)	C++17	52.32 / 100	1299 ms	1032 KiB

stations

#include "stations.h"
#include <bits/stdc++.h>
#define ll long long
#define sz(x) (int)(x).size()
using namespace std;

const int maxn = 1005;
int tin[maxn], tout[maxn], tr=-1;
vector<int> edges[maxn];

void dfs(int c, int p)
{
	tin[c]=++tr;
	for (int i : edges[c])
		if (i!=p)
			dfs(i,c);
	tout[c]=tr;
}

std::vector<int> label(int n, int k, vector<int> u, vector<int> v) {
	vector<int> labels(n);
	tr=-1;
	for (int i=0;i<n;++i)
		edges[i].clear();
	for (int i=0;i<n-1;++i)
	{
		edges[u[i]].push_back(v[i]);
		edges[v[i]].push_back(u[i]);
	}
	dfs(0,-1);
	for (int i = 0; i < n; i++) {
		labels[i] = tin[i]*1000+tout[i];
	}
	return labels;
}

int find_next_station(int s, int t, std::vector<int> c)
{
	/**cout<<s<<" "<<t<<"!\n";
	for (int i : c)
		cout<<i<<" ";
	cout<<"\n";**/
	if ((s/1000)<=(t/1000)&&(t%1000)<=(s%1000))
	{
		for (int i : c)
		{
			if ((i/1000)<=(t/1000)&&(t%1000)<=(i%1000)&&(s/1000)<=(i/1000)&&(i%1000)<=(s%1000))
				return i;
		}
	}
	else
	{
		for (int i : c)
		{
			if ((i/1000)<=(s/1000)&&(s%1000)<=(i%1000))
				return i;
		}
	}
	return 3141;
}
/**
int main()
{
	int n,k,x,y,q;
	cin>>n>>k;
	vector<int> a,b,v;
	for (int i=1;i<n;++i)
	{
		cin>>x>>y;
		a.push_back(x);
		b.push_back(y);
	}
	vector<int> ans = label(n,k,a,b);
	for (int i : ans)
	{
		cout<<i<<" "<<i/1000<<" "<<i%1000<<"\n";
	}
	cout<<"\n";
	cin>>q;
	while (q--)
	{
		cin>>x>>y;
		v.clear();
		for (int i=0;i<n-1;++i)
		{
			if (x==a[i])
				v.push_back(ans[b[i]]);
			if (x==b[i])
				v.push_back(ans[a[i]]);
		}
		//x = find_next_station(ans[x], ans[y], v);
		cout<<find_next_station(ans[x], ans[y], v)<<"\n";
	}
}**/

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