oj.uz

답안 #928806

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
928806 2024-02-17T06:03:07 Z KitasCraft 기지국 (IOI20_stations) C++17
0 / 100
 2288 ms 2097152 KB 
#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.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 1553 ms 2097152 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 7 ms 772 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #3
0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 1436 ms 2097152 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 502 ms 688 KB Output is correct
2 Runtime error 1236 ms 2097152 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #5
0 / 61.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 2288 ms 2097152 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -