Submission #348583

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
348583	2021-01-15 08:59:09	denkendoemeer	Swapping Cities (APIO20_swap)	C++14	100 / 100	370 ms	38152 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<bits/stdc++.h>
#include "swap.h"
#define ll long long
const int inf=1e9;
using namespace std;
vector<pair<int,pair<int,int>>>ed;
vector<pair<int,int>>dsu[100005];
int ans[100005],t[100005];
vector<int>g[100005];
void init(int n,int m,vector<int>x,vector<int>y,vector<int>w)
{
    int i;
    for(i=0;i<n;i++)
        ans[i]=inf;
    for(i=0;i<n;i++){
        dsu[i].push_back({0,i});
        g[i].push_back(i);
    }
    for(i=0;i<m;i++)
        ed.push_back({w[i],{y[i],x[i]}});
    sort(ed.begin(),ed.end());
    for(auto &it:ed){
        int y,x,w;
        y=it.second.first;
        x=it.second.second;
        w=it.first;
        int ty=dsu[y].back().second,tx=dsu[x].back().second;
        if (ty==tx){
            ans[ty]=min(ans[ty],w);
            continue;
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
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