Submission #802405

#	Time	Username	Problem	Language	Result	Execution time	Memory
802405		I_Love_EliskaM_	Stations (IOI20_stations)	C++14	60.32 / 100	819 ms	972 KiB

stations

#include "stations.h"
#include <bits/stdc++.h>
using namespace std;
#define forn(i,n) for(int i=0;i<n;++i)
#define pb push_back
#define all(x) x.begin(), x.end()
using ll = long long;

const int N=1e3;
int l[N], r[N];
vector<int> adj[N];
int nxt=0;
void dfs(int u, int p) {
	l[u]=r[u]=nxt++;
	for(auto&v:adj[u]) {
		if (v==p) continue;
		dfs(v,u);
		r[u]=max(r[u],r[v]);
	}
}

vector<int> label(int n, int k, vector<int>u, vector<int> v) {
	forn(i,n) adj[i].clear(); nxt=0;
	forn(i,n-1) {
		adj[u[i]].pb(v[i]);
		adj[v[i]].pb(u[i]);
	}

	//int mx=0;
	//forn(i,n) mx=max(mx,(int)adj[i].size());
	//if (mx==2) {
	//	forn(i,n) {
	//		if (adj[i].size()==1) {
	//			dfs(i,-1);
	//			break;
	//		}
	//	}
	//	vector<int> z(n); forn(i,n) z[i]=l[i];
	//	return z;
	//}

	int zzz=1;
	forn(i,n-1) {
		zzz&=(u[i]==i+1 && v[i]==i/2) || (u[i]==i/2 && v[i]==i+1);
	}
	if (zzz) {
		vector<int> z(n);
		forn(i,n) z[i]=i;
		return z;
	}

	dfs(0,-1);
	vector<int> ans(n);
	forn(i,n) ans[i]=l[i]+N*r[i];
	return ans;
}

bitset<N> can[N];
void dfs(int u) {
	can[u][u]=1;
	if (2*u+1 < N) {
		dfs(2*u+1);
		can[u]|=can[2*u+1];
	}
	if (2*u+2 < N) {
		dfs(2*u+2);
		can[u]|=can[2*u+2];
	}
}

int called=1;

int find_next_station(int s, int t, vector<int> adj) {
	if (adj.size()==1) return adj[0];
	//if (adj.size()==2) {
	//	if (adj[0]==s-1 && adj[1]==s+1) {
	//		if (s<t) return adj[1];
	//		else return adj[0];
	//	}
	//}
	if (called) {
		dfs(0);
		called=0;
	}
	if (max(s,t)<N) {
		if (can[s][t]) {
			if (can[2*s+1][t]) return 2*s+1;
			else return 2*s+2;
		} else return (s-1)/2;
	}

	int l=s%N, r=s/N;
	int lx=t%N, rx=t/N;
	if (l<=lx && rx<=r) {
		for(auto&x:adj) {
			int lq=x%N, rq=x/N;
			if (lq<l) continue;
			if (lq<=lx && rx<=rq) return x;
		}
	} else {
		for(auto&x:adj) {
			int lq=x%N, rq=x/N;
			if (lq<l) return x;
		}
	}
	//assert(0);
	exit(1);
}

Compilation message (stderr)

stations.cpp: In function 'std::vector<int> label(int, int, std::vector<int>, std::vector<int>)':
stations.cpp:4:19: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
    4 | #define forn(i,n) for(int i=0;i<n;++i)
      |                   ^~~
stations.cpp:23:2: note: in expansion of macro 'forn'
   23 |  forn(i,n) adj[i].clear(); nxt=0;
      |  ^~~~
stations.cpp:23:28: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   23 |  forn(i,n) adj[i].clear(); nxt=0;
      |                            ^~~
stations.cpp: In function 'int find_next_station(int, int, std::vector<int>)':
stations.cpp:102:16: warning: unused variable 'rq' [-Wunused-variable]
  102 |    int lq=x%N, rq=x/N;
      |                ^~

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