제출 #772648

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
772648		cadmiumsky	기지국 (IOI20_stations)	C++17	100 / 100	811 ms	876 KiB

stations

#include <bits/stdc++.h>
#define all(x) (x).begin(),(x).end()
using namespace std;

using ll = long long;
using ld = long double;

//#define int ll
#define sz(x) ((int)(x).size())

using pii = pair<int,int>;
using tii = tuple<int,int,int>;

const int nmax = 1e3 + 5;

vector<int> g[nmax];
int pin[nmax], pout[nmax], d[nmax];

int p = 0;
void dfs(int node, int f) {
  pin[node] = p++;
  d[node] = d[f] ^ 1;
  //cerr << node << ' ' << f << '\n';
  for(auto x : g[node])
    if(x != f) dfs(x, node);
  pout[node] = p++;
}

std::vector<int> label(int n, int k, std::vector<int> u, std::vector<int> v) {
  for(int i = 0; i < n; i++) g[i].clear();
  p = 0;
  for(int i = 0; i < sz(u); i++)
    g[u[i]].emplace_back(v[i]),
    g[v[i]].emplace_back(u[i]);
  dfs(0, 0);
  vector<int> rez(n);
  for(int i = 0; i < n; i++)
    rez[i] = (d[i]? pin[i] : pout[i]);
  map<int, int> freq;
  int cnt = 0;
  for(auto x : rez) freq[x];
  for(auto &[a, b] : freq) b = cnt++;
  for(auto &x : rez) x = freq[x];
  //for(int i = 0; i < n; i++) cerr << i << " --> " << rez[i] << '\n';
    
  return rez;
}
int find_next_station(int s, int t, std::vector<int> c) {
  if(sz(c) == 1) return c[0];
  if(s < c[0]) {
    //cerr << s << " --> " << t << '\n';
    //for(auto x : c) cerr << x << ' ';
    //cerr << '\n';
    if(t < s || rbegin(c)[1] < t) return c.back();
    for(int i = 0; i < sz(c); i++)
      if(t <= c[i]) return c[i];
    //assert(true == false);
  }
  else {
    if(t > s || t < c[1]) return c[0];
    int n = sz(c);
    c.emplace_back(s);
    for(int i = 1; i < n; i++) {
      if(c[i] <= t && t < c[i + 1]) return c[i];
    }
    //cerr << s << ' ' << t << '\n';
    //c.pop_back();
    //for(auto x : c) cerr << x << ' ';
    //cerr << '\n';
    //assert(true == false);
  }
  assert(false);
}

/**
      Anul asta se da centroid.
-- Surse oficiale
*/

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