제출 #1209610

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1209610		loom	City Mapping (NOI18_citymapping)	C++20	100 / 100	14 ms	5960 KiB

citymapping

#include "citymapping.h"
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define inf 5e18

const ll N = 1001;
vector<pair<ll,ll>> g[N];
ll sz[N], hvy[N], no[N];
ll dist[N][N];

void dfs(ll v){
   sz[v] = 1;
   hvy[v] = 0;
   ll mx = 0;

   for(auto [ch, w] : g[v]){
      if(no[ch]) continue;

      dfs(ch);
      sz[v] += sz[ch];
      
      if(mx < sz[ch]){
         mx = sz[ch];
         hvy[v] = ch;
      }
   }
}

ll leaf(ll v){
   if(hvy[v] == 0) return v;
   return leaf(hvy[v]);
}

ll dis(ll a, ll b){
   if(a == b) return 0;
   if(a > b) swap(a, b);

   if(dist[a][b]) return dist[a][b];
   return dist[a][b] = get_distance(a, b);
}

ll find(ll v, ll d){
   if(dis(1, v) == d) return v;
   return find(hvy[v], d);
}

bool cmp(ll a, ll b){
   return dis(1, a) < dis(1, b);
}
 
void find_roads(int n, int Q, int A[], int B[], int W[]){
	ll a[n];
   iota(a, a+n, 1);
   sort(a, a+n, cmp);

   for(ll i=1; i<n; i++){
      fill(no, no+N, 0);
      ll x = a[i], r = 1;

      while(1){
         dfs(r);
         ll l = leaf(r);
         if(l == r) break;

         r = find(r, (dis(1, l) + dis(1, x) - dis(x, l))/2);
         no[hvy[r]] = 1;
      }

      A[i-1] = r;
      B[i-1] = x;
      W[i-1] = dis(1, x) - dis(1, r);
      g[r].push_back({x, W[i-1]});
   }
}

• Subtask 1: 9 / 9
• Subtask 2: 16 / 16
• Subtask 3: 13 / 13
• Subtask 4: 19 / 19
• Subtask 5: 43 / 43