Submission #305107

#	Time	Username	Problem	Language	Result	Execution time	Memory
305107		Gajowy	Stations (IOI20_stations)	C++14	100 / 100	1236 ms	1152 KiB

stations

#pragma GCC optimize("Ofast")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
#define mp make_pair
#define eb emplace_back
#define pb push_back
#define e1 first
#define e2 second
#define uint unsigned int
#define ll long long
#define ull unsigned long long
#define ld long double
#define float long double
#define size(x) (int)x.size()
#define satori int testCases; cin>>testCases; while(testCases--)
#define fastio ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define all(r) begin(r),end(r)
#define time chrono::high_resolution_clock().now().time_since_epoch().count()
typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;

const int MAXN=1e3+10;

int id[MAXN],ct;
vector<int> g[MAXN];

void dfs(int u,int p,int d)
{
	if(d)
		id[u]=ct++;
	for(auto v:g[u])
		if(v!=p)
			dfs(v,u,d^1);
	if(!d)
		id[u]=ct++;
}

vector<int> label(int n,int k,vector<int> a,vector<int> b)
{
	vector<int> res(n); 
	for(int i=0;i<n;i++)
		g[i].clear();
	ct=0;
	for(int i=0;i<n-1;i++)
		g[a[i]].eb(b[i]),g[b[i]].eb(a[i]);
	ct=0;
	dfs(0,-1,0);
	for(int i=0;i<n;i++)
		res[i]=id[i];
	return res;
}


int find_next_station(int s,int t,vector<int> c)
{
	if(size(c)==1)
		return c[0];
	if(s<c[0])
	{
		if(t<s)
			return c.back();
		for(auto xd:c)
			if(xd>=t)
				return xd;
		return c.back();
	}
	else
	{
		if(t>s)
			return c[0];
		reverse(all(c));
		for(auto xd:c)
			if(xd<=t)
				return xd;
		return c.back();
	}
	return -1;
}

Compilation message (stderr)

stations.cpp:2: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
    2 | #pragma GCC optimization ("O3")
      | 
stations.cpp:3: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
    3 | #pragma GCC optimization ("unroll-loops")
      |

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