Submission #601888

#	Time	Username	Problem	Language	Result	Execution time	Memory
601888		yutabi	Stations (IOI20_stations)	C++14	0 / 100	870 ms	676 KiB

stations

#include "stations.h"
#include <bits/stdc++.h>
using namespace std;


#define pb push_back


int n;

vector <vector <int> > tree;
vector <int> ans;
vector <int> sz;


int DFS0(int node, int par)
{
	int sum=1;

	for(int i=0;i<tree[node].size();i++)
	{
		if(tree[node][i]!=par)
		{
			sum+=DFS0(tree[node][i],node);
		}
	}

	sz[node]=sum;

	return sum;
}

void DFS(int l, int r, int node, int par, int mode)
{
	if(mode==0)
	{
		ans[node]=l;

		l++;
	}

	else
	{
		ans[node]=r;

		r--;
	}

	for(int i=0;i<tree[node].size();i++)
	{
		if(tree[node][i]!=par)
		{
			if(mode==0)
			{
				DFS(l,l+sz[tree[node][i]]-1,tree[node][i],node,1);

				l+=sz[tree[node][i]];
			}

			else
			{
				DFS(r-sz[tree[node][i]]+1,r,tree[node][i],node,0);

				r-=sz[tree[node][i]];
			}
		}
	}

	return;
}



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

	tree.clear();
	tree.resize(n);
	ans.resize(n);
	sz.resize(n);

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

	DFS0(0,-1);
	DFS(0,k-1,0,-1,0);

	/*printf("\n");

	for(int i=0;i<n;i++)
	{
		printf("%d ",ans[i]);
	}

	printf("\n\n");*/

	return ans;
}

int find_next_station(int s, int t, std::vector<int> c)
{
	if(s<c[0])
	{
		if(t<s)
		{
			return c.back();
		}

		for(int i=0;i<c.size();i++)
		{
			if(t<=c[i])
			{
				return c[i];
			}
		}
	}

	if(s<t)
	{
		return c[0];
	}

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

Compilation message (stderr)

stations.cpp: In function 'int DFS0(int, int)':
stations.cpp:20:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   20 |  for(int i=0;i<tree[node].size();i++)
      |              ~^~~~~~~~~~~~~~~~~~
stations.cpp: In function 'void DFS(int, int, int, int, int)':
stations.cpp:49:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   49 |  for(int i=0;i<tree[node].size();i++)
      |              ~^~~~~~~~~~~~~~~~~~
stations.cpp: In function 'int find_next_station(int, int, std::vector<int>)':
stations.cpp:113:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  113 |   for(int i=0;i<c.size();i++)
      |               ~^~~~~~~~~
stations.cpp:134:1: warning: control reaches end of non-void function [-Wreturn-type]
  134 | }
      | ^

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