Submission #1239725

#	Time	Username	Problem	Language	Result	Execution time	Memory
1239725		SalihSahin	기지국 (IOI20_stations)	C++20	0 / 100	2157 ms	2162688 KiB

stations

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

vector<int> leaf, p;
vector<vector<int> > adj;

void dfs(int node, int par){
   p[node] = par;
   if(node != par && adj[node].size() == 1){
      leaf.push_back(node);
   }
   for(auto itr: adj[node]){
      if(itr == par) continue;
      dfs(itr, node);
   }
}

vector<int> label(int n, int k, vector<int> u, vector<int> v) {
   adj.resize(n);
   p.resize(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, 0);

   int now = 0;
   vector<int> labels(n), cnt(n);
   labels[0] = n-1;
   
   for(auto itr: leaf){
      int cur = itr;

      while(p[cur] != cur){
         labels[cur] = now++;
         cnt[p[cur]]++;
         if(cnt[p[cur]] == adj[p[cur]].size()-1){
            cur = p[cur];
         }
         else{
            break;
         }
      }
   }
   /*
   for(int i = 0; i < n; i++){
      cout<<i<<" -> "<<labels[i]<<endl;
   }*/

   return labels;
}

int find_next_station(int s, int t, vector<int> c) {
   int nxt = c.back();
   for(auto itr: c){
      if(itr >= t){
         nxt = itr;
         break;
      }
   }

   return nxt;
}

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