제출 #1239798

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1239798		SalihSahin	Stations (IOI20_stations)	C++20	100 / 100	309 ms	592 KiB

stations

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

vector<int> lab;
vector<vector<int> > adj;
int tval;

void dfs(int node, int par, int x){
   if(x) lab[node] = tval++;
   for(auto itr: adj[node]){
      if(itr == par) continue;
      dfs(itr, node, (x^1));
   }
   if(!x) lab[node] = tval++;
}

vector<int> label(int n, int k, vector<int> u, vector<int> v) {
   lab.assign(n, 0);
   adj.resize(n);
   tval = 0;
   for(int i = 0; i < n; i++){
      adj[i].clear();
   }

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

   return lab;
}

int find_next_station(int s, int t, vector<int> c) {
   if(s > c.back()) reverse(c.begin(), c.end());
   for(auto itr: c){
      if(min(itr, s) <= t && max(itr, s) >= t) return itr;
   }
   return c.back();
}

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