oj.uz

Submission #683038

# Submission time Handle Problem Language Result Execution time Memory
683038 2023-01-17T15:10:31 Z Nursik Swapping Cities (APIO20_swap) C++14
13 / 100
 425 ms 63124 KB 
#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, is[i] = 0;
    }
    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.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 47220 KB Output is correct
2 Correct 24 ms 47316 KB Output is correct
3 Correct 23 ms 47188 KB Output is correct
4 Correct 24 ms 47276 KB Output is correct
5 Correct 27 ms 47336 KB Output is correct
6 Correct 23 ms 47424 KB Output is correct
7 Correct 24 ms 47424 KB Output is correct
8 Correct 24 ms 47444 KB Output is correct
9 Correct 97 ms 57772 KB Output is correct
10 Correct 105 ms 59520 KB Output is correct
11 Correct 104 ms 59160 KB Output is correct
12 Correct 101 ms 59812 KB Output is correct
13 Correct 107 ms 59752 KB Output is correct
14 Correct 97 ms 56960 KB Output is correct
15 Correct 144 ms 60896 KB Output is correct
16 Correct 142 ms 60508 KB Output is correct
17 Correct 169 ms 61472 KB Output is correct
18 Correct 151 ms 61276 KB Output is correct
19 Correct 74 ms 52708 KB Output is correct
20 Correct 144 ms 62016 KB Output is correct
21 Correct 145 ms 61968 KB Output is correct
22 Correct 188 ms 62716 KB Output is correct
23 Correct 156 ms 62692 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 47220 KB Output is correct
2 Correct 24 ms 47316 KB Output is correct
3 Correct 377 ms 62568 KB Output is correct
4 Correct 315 ms 63124 KB Output is correct
5 Correct 425 ms 63052 KB Output is correct
6 Correct 321 ms 62952 KB Output is correct
7 Correct 359 ms 63056 KB Output is correct
8 Correct 320 ms 62548 KB Output is correct
9 Correct 350 ms 62836 KB Output is correct
10 Correct 308 ms 62420 KB Output is correct

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 47220 KB Output is correct
2 Correct 24 ms 47316 KB Output is correct
3 Correct 23 ms 47188 KB Output is correct
4 Correct 24 ms 47276 KB Output is correct
5 Correct 27 ms 47336 KB Output is correct
6 Correct 23 ms 47424 KB Output is correct
7 Correct 24 ms 47424 KB Output is correct
8 Correct 24 ms 47444 KB Output is correct
9 Correct 21 ms 47188 KB Output is correct
10 Correct 23 ms 47324 KB Output is correct
11 Correct 23 ms 47416 KB Output is correct
12 Correct 26 ms 47436 KB Output is correct
13 Correct 28 ms 47444 KB Output is correct
14 Correct 31 ms 47312 KB Output is correct
15 Incorrect 29 ms 47376 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 47188 KB Output is correct
2 Correct 24 ms 47220 KB Output is correct
3 Correct 24 ms 47316 KB Output is correct
4 Correct 23 ms 47188 KB Output is correct
5 Correct 24 ms 47276 KB Output is correct
6 Correct 27 ms 47336 KB Output is correct
7 Correct 23 ms 47424 KB Output is correct
8 Correct 24 ms 47424 KB Output is correct
9 Correct 24 ms 47444 KB Output is correct
10 Correct 97 ms 57772 KB Output is correct
11 Correct 105 ms 59520 KB Output is correct
12 Correct 104 ms 59160 KB Output is correct
13 Correct 101 ms 59812 KB Output is correct
14 Correct 107 ms 59752 KB Output is correct
15 Correct 23 ms 47324 KB Output is correct
16 Correct 23 ms 47416 KB Output is correct
17 Correct 26 ms 47436 KB Output is correct
18 Correct 28 ms 47444 KB Output is correct
19 Correct 31 ms 47312 KB Output is correct
20 Incorrect 29 ms 47376 KB Output isn't correct
21 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 47220 KB Output is correct
2 Correct 24 ms 47316 KB Output is correct
3 Correct 23 ms 47188 KB Output is correct
4 Correct 24 ms 47276 KB Output is correct
5 Correct 27 ms 47336 KB Output is correct
6 Correct 23 ms 47424 KB Output is correct
7 Correct 24 ms 47424 KB Output is correct
8 Correct 24 ms 47444 KB Output is correct
9 Correct 97 ms 57772 KB Output is correct
10 Correct 105 ms 59520 KB Output is correct
11 Correct 104 ms 59160 KB Output is correct
12 Correct 101 ms 59812 KB Output is correct
13 Correct 107 ms 59752 KB Output is correct
14 Correct 97 ms 56960 KB Output is correct
15 Correct 144 ms 60896 KB Output is correct
16 Correct 142 ms 60508 KB Output is correct
17 Correct 169 ms 61472 KB Output is correct
18 Correct 151 ms 61276 KB Output is correct
19 Correct 377 ms 62568 KB Output is correct
20 Correct 315 ms 63124 KB Output is correct
21 Correct 425 ms 63052 KB Output is correct
22 Correct 321 ms 62952 KB Output is correct
23 Correct 359 ms 63056 KB Output is correct
24 Correct 320 ms 62548 KB Output is correct
25 Correct 350 ms 62836 KB Output is correct
26 Correct 308 ms 62420 KB Output is correct
27 Correct 23 ms 47324 KB Output is correct
28 Correct 23 ms 47416 KB Output is correct
29 Correct 26 ms 47436 KB Output is correct
30 Correct 28 ms 47444 KB Output is correct
31 Correct 31 ms 47312 KB Output is correct
32 Incorrect 29 ms 47376 KB Output isn't correct
33 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 47188 KB Output is correct
2 Correct 24 ms 47220 KB Output is correct
3 Correct 24 ms 47316 KB Output is correct
4 Correct 23 ms 47188 KB Output is correct
5 Correct 24 ms 47276 KB Output is correct
6 Correct 27 ms 47336 KB Output is correct
7 Correct 23 ms 47424 KB Output is correct
8 Correct 24 ms 47424 KB Output is correct
9 Correct 24 ms 47444 KB Output is correct
10 Correct 97 ms 57772 KB Output is correct
11 Correct 105 ms 59520 KB Output is correct
12 Correct 104 ms 59160 KB Output is correct
13 Correct 101 ms 59812 KB Output is correct
14 Correct 107 ms 59752 KB Output is correct
15 Correct 97 ms 56960 KB Output is correct
16 Correct 144 ms 60896 KB Output is correct
17 Correct 142 ms 60508 KB Output is correct
18 Correct 169 ms 61472 KB Output is correct
19 Correct 151 ms 61276 KB Output is correct
20 Correct 377 ms 62568 KB Output is correct
21 Correct 315 ms 63124 KB Output is correct
22 Correct 425 ms 63052 KB Output is correct
23 Correct 321 ms 62952 KB Output is correct
24 Correct 359 ms 63056 KB Output is correct
25 Correct 320 ms 62548 KB Output is correct
26 Correct 350 ms 62836 KB Output is correct
27 Correct 308 ms 62420 KB Output is correct
28 Correct 23 ms 47324 KB Output is correct
29 Correct 23 ms 47416 KB Output is correct
30 Correct 26 ms 47436 KB Output is correct
31 Correct 28 ms 47444 KB Output is correct
32 Correct 31 ms 47312 KB Output is correct
33 Incorrect 29 ms 47376 KB Output isn't correct
34 Halted 0 ms 0 KB -