제출 #291693

#	제출 시각UTC-0	아이디	문제	언어	결과	실행 시간	메모리
291693	2020-09-05 16:31:13	nvmdava	자매 도시 (APIO20_swap)	C++17	100 / 100	431 ms	31768 KiB

swap

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include "swap.h"
#include <bits/stdc++.h>
using namespace std;
const int N = 100005;
const int INF = 1000000005;
#define ff first
#define ss second
vector<pair<int, pair<int, int> > > edge;
vector<pair<int, int> > dsu[N];
int ans[N];
int d[N];
vector<int> gr[N];
void init(int N, int M,
          std::vector<int> U, std::vector<int> V, std::vector<int> W) {
  cerr<<"BEGIN";
  for(int i = 0; i < N; ++i)
    ans[i] = INF;
  for(int i = 0; i < N; ++i){
    dsu[i].push_back({0, i});
    gr[i].push_back(i);
  }
  for(int i = 0; i < M; ++i)
    edge.push_back({W[i], {V[i], U[i]}});
  sort(edge.begin(), edge.end());
  for(auto& wtf : edge){
    int v = wtf.ss.ff;
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

• Subtask 1: 6 / 6
• Subtask 2: 7 / 7
• Subtask 3: 17 / 17
• Subtask 4: 20 / 20
• Subtask 5: 23 / 23
• Subtask 6: 27 / 27