Submission #683035

#	Time	Username	Problem	Language	Result	Execution time	Memory
683035		Nursik	Swapping Cities (APIO20_swap)	C++14	13 / 100	427 ms	65564 KiB

swap

#include "swap.h"

#include <stdio.h>
 
#include <algorithm>
#include <bitset>
#include <cassert>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <deque>
#include <fstream>
#include <functional>
#include <iomanip>
#include <iostream>
#include <list>
#include <map>
#include <queue>
#include <random>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <vector>

using namespace std;

#define mp make_pair
#define f first
#define s second
#define pb push_back

const int maxn = 1e6 + 200;

int subtask2 = 1, subtask1 = 1, cycle = 0;
int used[maxn], p[maxn], sz[maxn], is[maxn], deg[maxn];
multiset<int> setik;
vector<pair<int, int>> g[maxn];
vector<int> g2[maxn];
int ver, reb;
vector<pair<int, pair<int, int>>> kektor;
int get(int v){
    if (v == p[v])
        return v;
    return p[v] = get(p[v]);
}
void unite(int a, int b){
    a = get(a), b = get(b);
    if (a == b){
        is[a] |= 1;
        return;
    }
    if (sz[a] > sz[b])
        swap(a, b);
    p[a] = b;
    sz[b] += sz[a];
    is[b] |= is[a];
}
void init(int n, int m, vector<int> u, vector<int> v, vector<int> w) {
    for (int i = 0; i < m; ++i){
        int x = u[i], y = v[i];
        g[x].pb(mp(y, w[i]));
        g[y].pb(mp(x, w[i]));
        kektor.pb(mp(w[i], mp(x, y)));
    }
    for (auto it : u){
        subtask2 &= (it == 0);
    }
    subtask2 &= (m == n - 1);
    for (auto it : w){
        setik.insert(it);
    }
    for (int i = 1; i <= n; ++i){
        int sz2 = (int)g[i].size();
        subtask1 &= (sz2 <= 2);
    }
    ver = n, reb = m;
    for (int i = 0; i < n; ++i){
        p[i] = i, sz[i] = 1;
    }
    sort(kektor.begin(), kektor.end());
}
int getMinimumFuelCapacity(int x, int y) {
    if (subtask2 == 1){
        if (x == 0){
            int cur = g[y][0].s;
            setik.erase(setik.find(cur));
            int sz2 = (int)setik.size();
            if (sz2 == 0){
                setik.insert(cur);
                return -1;
            }
            sz2 -= 1;
            int cur2 = *setik.begin();
            setik.erase(setik.find(cur2));
            if (sz2 == 0){
                setik.insert(cur);
                setik.insert(cur2);
                return -1;
            }    
            sz2 -= 1;
            int cur3 = *setik.begin();
            setik.insert(cur);
            setik.insert(cur2);
            return max({cur, cur2, cur3});
        }
        int cur = g[x][0].s;
        int cur2 = g[y][0].s;
        setik.erase(setik.find(cur));
        setik.erase(setik.find(cur2));
        if ((int)setik.size() == 0){
            setik.insert(cur);
            setik.insert(cur2);
            return -1;
        }
        int cur3 = *setik.begin();
        setik.insert(cur);
        setik.insert(cur2);
        return max({cur, cur2, cur3});
    }
    if (subtask1 == 1){
        if (reb == ver - 1){
            return -1;
        }
        else{
            return *setik.rbegin();
        }
    }
    for (int i = 0; i < ver; ++i){
        p[i] = i, sz[i] = 1;
    }
    for (auto it : kektor){
        pair<int, pair<int, int>> cur = it;
        int xu = cur.s.f, yu = cur.s.s;
        deg[xu] += 1;
        deg[yu] += 1;
        is[get(xu)] |= (deg[xu] >= 3);
        is[get(yu)] |= (deg[yu] >= 3);
        unite(xu, yu);
        if (get(x) == get(y) && is[get(x)]){
            return cur.f;
        }
    }
    return -1;
}

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