Submission #928806

#	Time	Username	Problem	Language	Result	Execution time	Memory
928806		KitasCraft	Stations (IOI20_stations)	C++17	0 / 100	2288 ms	2097152 KiB

stations

#include "stations.h"
#include <iostream>
#include <vector>
#include <algorithm>
#include <iterator>
#define pb push_back

using namespace std;

const int MAXN = 1e3;

int p[MAXN],sub[MAXN];
vector<int> ed[MAXN];

// dfs for counting subtree size
void dfs(const int &v) {
  sub[v]=1;
  for (const int &i : ed[v]) {
    if (i == p[v]) continue;
    p[i]=v;
    dfs(i);
    sub[v]+=sub[i];
  }
}

// construct the labelling while bringing the labels
// the node, min label in subtree, max label in the subtree, is current node with max label (true) or min label (false)
void con(const int &v,int l,const int &r,const bool &maks,vector<int> &lab) {
  if (maks) {
    // label v with max
    lab[v]=r;
  }
  else {
    // label v with min
    lab[v]=l;
    l++;
  }
  for (const int &i : ed[v]) {
    if (i == p[v]) continue;
    con(i,l,l+sub[i]-1,1-maks,lab);
    l+=sub[i];
  }
}

vector<int> label(int n, int k, vector<int> u, vector<int> v) {
  vector<int> perm(n,0);
  for (int i=0;i<n-1;i++) {
    ed[u[i]].pb(v[i]);
    ed[v[i]].pb(u[i]);
  }
  p[0]=-1;
  dfs(0);
  con(0,0,n-1,0,perm);
  return perm;
}


int find_next_station(int s, int t, vector<int> c) {
	int x=c.size();
	if (x == 1) return c[0];
	if (s < c[0]) {
		// this node is labeled min
		if (t < s || t > c[x-2]) return c[x-1];
		// thank you for making array c already sorted lmao
		return *lower_bound(c.begin(),c.end(),t);
	}
	else {
		// this node is labeled max
		if (t > s || t < c[1]) return c[0];
		return *(--upper_bound(c.begin(),c.end(),t));
	}
}

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