제출 #434388

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
434388		radaiosm7	기지국 (IOI20_stations)	C++17	0 / 100	3097 ms	350392 KiB

stations

#include "stations.h"
#include <vector>
#include <bits/stdc++.h>
using namespace std;

void dfs(int x, vector<int>& tin, vector<int>& tout, int& timer, vector<vector<int> >& adj, int p=-1) {
  tin[x] = timer++;
  for (auto y : adj[x]) {
    if (y != p) dfs(y, tin, tout, timer, adj, x);
  }
  tout[x] = timer++;
}

void give_label(int x, vector<int>& labels, vector<vector<int> >& adj, vector<int>& tin, vector<int>& tout, int p=-1, int curr=0) {
  labels[x] = (curr==0)?(tin[x]):(tout[x]);

  for (auto y : adj[x]) {
    if (y != p) {
      give_label(y, labels, adj, tin, tout, x, curr^1);
    }
  }
}

vector<int> label(int n, int k, vector<int> u, vector<int> v) {
  vector<int> tin(1005);
  vector<int> tout(1005);
  vector<vector<int> > adj(1005, vector<int> (1005));
  int timer = 0;
  vector<int> labels(n);

  for (int i=0; i < n-1; ++i) {
    adj[u[i]].push_back(v[i]);
    adj[v[i]].push_back(u[i]);
  }

  dfs(0, tin, tout, timer, adj);
	give_label(0, labels, adj, tin, tout);

	return labels;
}

int find_next_station(int s, int t, vector<int> c) {
	if ((int)c.size() == 1) {
    return c[0];
	}

	else if (s > c[(int)c.size()-1]) { //Then s is exit time
    if (t > s) {
      return c[0];
    }

    else {
      for (int i=1; i < (int)c.size()-1; ++i) {
        if (c[i] < t && t < c[i+1]) {
          return c[i];
        }
      }

      return c[(int)c.size()-1];
    }
	}

	else {
    if (c[(int)c.size()-2]+1 < t) {
      return c[(int)c.size()-1];
    }

    else {
      for (int i=1; i < (int)c.size(); ++i) {
        if (c[i-1] < t && t < c[i]) {
          return c[i];
        }
      }

      return c[0];
    }
	}
}

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