oj.uz

Submission #683035

# Submission time Handle Problem Language Result Execution time Memory
683035 2023-01-17T15:09:04 Z Nursik Swapping Cities (APIO20_swap) C++14
13 / 100
 427 ms 65564 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;
    }
    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 23 ms 47188 KB Output is correct
2 Correct 23 ms 47240 KB Output is correct
3 Correct 26 ms 47332 KB Output is correct
4 Correct 24 ms 47268 KB Output is correct
5 Correct 31 ms 47316 KB Output is correct
6 Correct 28 ms 47400 KB Output is correct
7 Correct 26 ms 47412 KB Output is correct
8 Correct 24 ms 47432 KB Output is correct
9 Correct 117 ms 57868 KB Output is correct
10 Correct 110 ms 60436 KB Output is correct
11 Correct 147 ms 60400 KB Output is correct
12 Correct 117 ms 61136 KB Output is correct
13 Correct 104 ms 61328 KB Output is correct
14 Correct 97 ms 58628 KB Output is correct
15 Correct 200 ms 63336 KB Output is correct
16 Correct 153 ms 63064 KB Output is correct
17 Correct 190 ms 63696 KB Output is correct
18 Correct 193 ms 63716 KB Output is correct
19 Correct 79 ms 54524 KB Output is correct
20 Correct 163 ms 64556 KB Output is correct
21 Correct 157 ms 64396 KB Output is correct
22 Correct 174 ms 65212 KB Output is correct
23 Correct 195 ms 65100 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 47188 KB Output is correct
2 Correct 23 ms 47240 KB Output is correct
3 Correct 366 ms 65072 KB Output is correct
4 Correct 362 ms 65552 KB Output is correct
5 Correct 386 ms 65420 KB Output is correct
6 Correct 390 ms 65448 KB Output is correct
7 Correct 407 ms 65564 KB Output is correct
8 Correct 427 ms 65064 KB Output is correct
9 Correct 412 ms 65344 KB Output is correct
10 Correct 384 ms 64992 KB Output is correct

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 47188 KB Output is correct
2 Correct 23 ms 47240 KB Output is correct
3 Correct 26 ms 47332 KB Output is correct
4 Correct 24 ms 47268 KB Output is correct
5 Correct 31 ms 47316 KB Output is correct
6 Correct 28 ms 47400 KB Output is correct
7 Correct 26 ms 47412 KB Output is correct
8 Correct 24 ms 47432 KB Output is correct
9 Correct 25 ms 47184 KB Output is correct
10 Correct 28 ms 47420 KB Output is correct
11 Correct 31 ms 47444 KB Output is correct
12 Correct 30 ms 47428 KB Output is correct
13 Correct 24 ms 47428 KB Output is correct
14 Correct 29 ms 47432 KB Output is correct
15 Incorrect 26 ms 47444 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 47184 KB Output is correct
2 Correct 23 ms 47188 KB Output is correct
3 Correct 23 ms 47240 KB Output is correct
4 Correct 26 ms 47332 KB Output is correct
5 Correct 24 ms 47268 KB Output is correct
6 Correct 31 ms 47316 KB Output is correct
7 Correct 28 ms 47400 KB Output is correct
8 Correct 26 ms 47412 KB Output is correct
9 Correct 24 ms 47432 KB Output is correct
10 Correct 117 ms 57868 KB Output is correct
11 Correct 110 ms 60436 KB Output is correct
12 Correct 147 ms 60400 KB Output is correct
13 Correct 117 ms 61136 KB Output is correct
14 Correct 104 ms 61328 KB Output is correct
15 Correct 28 ms 47420 KB Output is correct
16 Correct 31 ms 47444 KB Output is correct
17 Correct 30 ms 47428 KB Output is correct
18 Correct 24 ms 47428 KB Output is correct
19 Correct 29 ms 47432 KB Output is correct
20 Incorrect 26 ms 47444 KB Output isn't correct
21 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 47188 KB Output is correct
2 Correct 23 ms 47240 KB Output is correct
3 Correct 26 ms 47332 KB Output is correct
4 Correct 24 ms 47268 KB Output is correct
5 Correct 31 ms 47316 KB Output is correct
6 Correct 28 ms 47400 KB Output is correct
7 Correct 26 ms 47412 KB Output is correct
8 Correct 24 ms 47432 KB Output is correct
9 Correct 117 ms 57868 KB Output is correct
10 Correct 110 ms 60436 KB Output is correct
11 Correct 147 ms 60400 KB Output is correct
12 Correct 117 ms 61136 KB Output is correct
13 Correct 104 ms 61328 KB Output is correct
14 Correct 97 ms 58628 KB Output is correct
15 Correct 200 ms 63336 KB Output is correct
16 Correct 153 ms 63064 KB Output is correct
17 Correct 190 ms 63696 KB Output is correct
18 Correct 193 ms 63716 KB Output is correct
19 Correct 366 ms 65072 KB Output is correct
20 Correct 362 ms 65552 KB Output is correct
21 Correct 386 ms 65420 KB Output is correct
22 Correct 390 ms 65448 KB Output is correct
23 Correct 407 ms 65564 KB Output is correct
24 Correct 427 ms 65064 KB Output is correct
25 Correct 412 ms 65344 KB Output is correct
26 Correct 384 ms 64992 KB Output is correct
27 Correct 28 ms 47420 KB Output is correct
28 Correct 31 ms 47444 KB Output is correct
29 Correct 30 ms 47428 KB Output is correct
30 Correct 24 ms 47428 KB Output is correct
31 Correct 29 ms 47432 KB Output is correct
32 Incorrect 26 ms 47444 KB Output isn't correct
33 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 47184 KB Output is correct
2 Correct 23 ms 47188 KB Output is correct
3 Correct 23 ms 47240 KB Output is correct
4 Correct 26 ms 47332 KB Output is correct
5 Correct 24 ms 47268 KB Output is correct
6 Correct 31 ms 47316 KB Output is correct
7 Correct 28 ms 47400 KB Output is correct
8 Correct 26 ms 47412 KB Output is correct
9 Correct 24 ms 47432 KB Output is correct
10 Correct 117 ms 57868 KB Output is correct
11 Correct 110 ms 60436 KB Output is correct
12 Correct 147 ms 60400 KB Output is correct
13 Correct 117 ms 61136 KB Output is correct
14 Correct 104 ms 61328 KB Output is correct
15 Correct 97 ms 58628 KB Output is correct
16 Correct 200 ms 63336 KB Output is correct
17 Correct 153 ms 63064 KB Output is correct
18 Correct 190 ms 63696 KB Output is correct
19 Correct 193 ms 63716 KB Output is correct
20 Correct 366 ms 65072 KB Output is correct
21 Correct 362 ms 65552 KB Output is correct
22 Correct 386 ms 65420 KB Output is correct
23 Correct 390 ms 65448 KB Output is correct
24 Correct 407 ms 65564 KB Output is correct
25 Correct 427 ms 65064 KB Output is correct
26 Correct 412 ms 65344 KB Output is correct
27 Correct 384 ms 64992 KB Output is correct
28 Correct 28 ms 47420 KB Output is correct
29 Correct 31 ms 47444 KB Output is correct
30 Correct 30 ms 47428 KB Output is correct
31 Correct 24 ms 47428 KB Output is correct
32 Correct 29 ms 47432 KB Output is correct
33 Incorrect 26 ms 47444 KB Output isn't correct
34 Halted 0 ms 0 KB -