Submission #311941

#	Time	Username	Problem	Language	Result	Execution time	Memory
311941		Mackerel_Pike	Stations (IOI20_stations)	C++14	100 / 100	1184 ms	1116 KiB

stations

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

using namespace std;

#define FOR(i, x, y) for(int i = (x); i < (y); ++i)
#define REP(i, x, y) for(int i = (x); i <= (y); ++i)
#define PB push_back
#define MP make_pair
#define PH push
#define fst first
#define snd second
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef long double ldb;
typedef pair<int, int> pii;

const int maxn = 1005;

int clk = 0;
int in[maxn], out[maxn];
vector<int> ans;
vector<int> g[maxn];

void dfs(int u, int p, int d){
	in[u] = ++clk;
	FOR(i, 0, g[u].size()){
		int v = g[u][i];
		if(v == p)
			continue;
		dfs(v, u, d + 1);
	}
	out[u] = ++clk;
	if(d & 1)
		ans[u] = out[u];
	else
		ans[u] = in[u];
	return;
}

vector<int> label(int n, int k, vector<int> u, vector<int> v){
	FOR(i, 0, n)	
		g[i].clear();
	clk = 0;
	FOR(i, 0, n - 1){
		int u_ = u[i], v_ = v[i];
		g[u_].PB(v_);
		g[v_].PB(u_);
	}
	
	ans.resize(n);
	dfs(0, -1, 0);	
	vector<int> tmp = ans;
	sort(tmp.begin(), tmp.end());
	FOR(i, 0, n)
		ans[i] = lower_bound(tmp.begin(), tmp.end(), ans[i]) - tmp.begin();
	return ans;
}

int find_next_station(int s, int t, vector<int> c){
	if(s <= c[0]){
		FOR(i, 0, c.size() - 1) if(t >= s && t <= c[i])
			return c[i];
		return c[c.size() - 1];
	}
	else{
		for(int i = c.size() - 1; i; --i) if(t >= c[i] && t <= s)
			return c[i];
		return c[0];
	}
}

Compilation message (stderr)

stations.cpp: In function 'void dfs(int, int, int)':
stations.cpp:6:41: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    6 | #define FOR(i, x, y) for(int i = (x); i < (y); ++i)
      |                                         ^
stations.cpp:28:2: note: in expansion of macro 'FOR'
   28 |  FOR(i, 0, g[u].size()){
      |  ^~~
stations.cpp: In function 'int find_next_station(int, int, std::vector<int>)':
stations.cpp:6:41: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    6 | #define FOR(i, x, y) for(int i = (x); i < (y); ++i)
      |                                         ^
stations.cpp:63:3: note: in expansion of macro 'FOR'
   63 |   FOR(i, 0, c.size() - 1) if(t >= s && t <= c[i])
      |   ^~~

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