oj.uz

Submission #1106481

# Submission time Handle Problem Language Result Execution time Memory
1106481 2024-10-30T12:45:20 Z vladilius Swapping Cities (APIO20_swap) C++17
0 / 100
 425 ms 524288 KB 
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
#define pb push_back
#define ff first
#define ss second
#define arr3 array<int, 3>

struct dsu{
    vector<int> p, d;
    vector<bool> f;
    vector<vector<int>> A, out;
    int n;
    void init(int ns){
        n = ns;
        d.resize(n + 1);
        p.resize(n + 1);
        f.resize(n + 1);
        A.resize(n + 1);
        out.resize(n + 1);
        for (int i = 1; i <= n; i++){
            out[i].assign(n + 1, -1);
            p[i] = i;
            A[i] = {i};
        }
    }
    int get(int v){
        if (p[v] != v){
            p[v] = get(p[v]);
        }
        return p[v];
    }
    void unite(int x, int y, int w){
        int a = get(x), b = get(y);
        if (a == b){
            if (!f[a]){
                f[a] = 1;
                for (int i: A[a]){
                    for (int j: A[a]){
                        out[i][j] = w;
                    }
                }
            }
            return;
        }
        if (A[a].size() > A[b].size()) swap(a, b);
        
        if (f[a] || f[b] || d[x] == 2 || d[y] == 2){
            for (int i: A[a]){
                for (int j: A[b]){
                    out[i][j] = out[j][i] = w;
                }
            }
            f[b] = 1;
        }
        else {
            d[x]++; d[y]++;
        }
        
        for (int i: A[a]) A[b].pb(i);
        p[a] = b;
    }
};

dsu T;
int n, m;

void init(int N, int M, vector<int> U, vector<int> V, vector<int> W){
    n = N; m = M;
    vector<arr3> ed;
    for (int i = 0; i < m; i++){
        ed.pb({W[i], U[i] + 1, V[i] + 1});
    }
    sort(ed.begin(), ed.end());
    T.init(n);
    for (auto [f, x, y]: ed){
        T.unite(x, y, f);
    }
    
    bool ind = 0;
    for (int i = 1; i <= n; i++){
        for (int j = i + 1; j <= n; j++){
            if (T.out[i][j] == -1){
                ind = 1;
                break;
            }
        }
        if (ind) break;
    }
    
    if (ind){
        assert(m == (n - 1));
        vector<int> d(n);
        for (int i = 0; i < m; i++){
            d[U[i]]++; d[V[i]]++;
        }
        for (int i = 0; i < n; i++){
            assert(d[i] == 1 || d[i] == 2);
        }
    }
}

int getMinimumFuelCapacity(int x, int y){
    x++; y++;
    return T.out[x][y];
}

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 1104 KB Output is correct
5 Correct 3 ms 3920 KB Output is correct
6 Correct 3 ms 3664 KB Output is correct
7 Correct 3 ms 4448 KB Output is correct
8 Correct 3 ms 4432 KB Output is correct
9 Runtime error 373 ms 524288 KB Execution killed with signal 9
10 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Runtime error 425 ms 524288 KB Execution killed with signal 9
4 Halted 0 ms 0 KB -

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 1104 KB Output is correct
5 Correct 3 ms 3920 KB Output is correct
6 Correct 3 ms 3664 KB Output is correct
7 Correct 3 ms 4448 KB Output is correct
8 Correct 3 ms 4432 KB Output is correct
9 Correct 1 ms 336 KB Output is correct
10 Runtime error 11 ms 8696 KB Execution killed with signal 6
11 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 1 ms 1104 KB Output is correct
6 Correct 3 ms 3920 KB Output is correct
7 Correct 3 ms 3664 KB Output is correct
8 Correct 3 ms 4448 KB Output is correct
9 Correct 3 ms 4432 KB Output is correct
10 Runtime error 373 ms 524288 KB Execution killed with signal 9
11 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 1104 KB Output is correct
5 Correct 3 ms 3920 KB Output is correct
6 Correct 3 ms 3664 KB Output is correct
7 Correct 3 ms 4448 KB Output is correct
8 Correct 3 ms 4432 KB Output is correct
9 Runtime error 373 ms 524288 KB Execution killed with signal 9
10 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 1 ms 1104 KB Output is correct
6 Correct 3 ms 3920 KB Output is correct
7 Correct 3 ms 3664 KB Output is correct
8 Correct 3 ms 4448 KB Output is correct
9 Correct 3 ms 4432 KB Output is correct
10 Runtime error 373 ms 524288 KB Execution killed with signal 9
11 Halted 0 ms 0 KB -