Submission #1080550

#	Time	Username	Problem	Language	Result	Execution time	Memory
1080550		Faisal_Saqib	Stations (IOI20_stations)	C++17	100 / 100	633 ms	1188 KiB

stations

#include "stations.h"
#include <vector>
#include <bits/stdc++.h>
using namespace std;
const int N=1e3+100;
const int M=1e3;
vector<int> ma[N];
int tin[N],tout[N],last[N],timer=-1;
void dfs(int v, int p,int h=0)
{
    tin[v] = ++timer; // n

    for (auto u:ma[v]) {
        if (u != p)
        {
            dfs(u, v,1-h);
        }
    }
   	last[v]=h;
    tout[v] = ++timer; // n
}
std::vector<int> label(int n, int k, std::vector<int> u, std::vector<int> v) {
	timer=-1;
	for(int i=0;i<(n);i++)last[i]=-1,ma[i].clear();
	vector<int> labels(n,0);
	for(int i=0;i<(n-1);i++)
	{
		ma[u[i]].push_back(v[i]);
		ma[v[i]].push_back(u[i]);
	}
	dfs(0,-1);
	// tout[i] >= tin[i]
	// tout[i]-tin[i] == sz[i]
	// 1<= sz[i] <=n

	for(int i=0;i<n;i++)
	{
		if(last[i]==0)
		{
			labels[i]=tin[i];
		}
		else
		{
			labels[i]=tout[i];
		}
	}
	sort(begin(labels),end(labels));
	vector<int> ans(n);
	for(int i=0;i<n;i++)
	{
		if(last[i]==0)
		{
			ans[i]=lower_bound(begin(labels),end(labels),tin[i])-begin(labels);
		}
		else
		{
			ans[i]=lower_bound(begin(labels),end(labels),tout[i])-begin(labels);
		}
	}
	return ans;
}
int find_next_station(int s, int t, std::vector<int> c) {
	sort(begin(c),end(c));
	if(s<c[0])
	{
		// s = in[s]
		int last=s+1;
		for(auto j:c)
		{
			if(last<=t and t<=j)
				return j;
			last=j+1;
		}
		return c.back();
	}
	else
	{
		reverse(begin(c),end(c));
		int last=s-1;
		for(auto j:c)
		{
			if(j<=t and t<=last)
				return j;
			last=j-1;
		}
		return c.back();
	}
	return t;
}

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