oj.uz

Submission #982525

# Submission time Handle Problem Language Result Execution time Memory
982525 2024-05-14T10:47:28 Z phoenix Swapping Cities (APIO20_swap) C++17
17 / 100
 84 ms 57288 KB 
#include <bits/stdc++.h>
#include "swap.h"

using namespace std;
using ll = long long;

const int N = 100100;
const int M = 200200;

const int INF = 1e9;

struct edge {
    int u;
    int v;
    int w;
};  

int bg[N + M];
int en[N + M];
int cap[N + M];
bool isbam[N + M];

int head[N + M];
int par[N + M][18];

vector<edge> edges;

int find(int x) {
    return head[x] = (head[x] == x ? x : find(head[x]));
};

vector<int> g[N];
int tin[N + M], tout[N + M], T;

void dfs(int s) {
    tin[s] = ++T;
    for (int to : g[s]) {
        dfs(to);
    }
    tout[s] = T;
}

bool up(int u, int v) {
    return tin[u] <= tin[v] && tout[u] >= tout[v];
}

void init(int N, int M,
          vector<int> U, vector<int> V, vector<int> W) {
    for (int i = 0; i < M; i++) {
        edges.push_back({U[i], V[i], W[i]});
    }
    
    sort(edges.begin(), edges.end(), [](edge x, edge y) {
        return x.w < y.w;
    });

    int lst = N - 1;
    for (int i = 0; i < N; i++) {
        bg[i] = en[i] = i;
        head[i] = i;
        isbam[i] = true;
    }
    for (auto e : edges) {
        lst++;
        int t1 = find(e.u);
        int t2 = find(e.v);

        head[lst] = par[lst][0] = lst;
        par[t1][0] = par[t2][0] = lst;
        head[t1] = head[t2] = lst;
        cap[lst] = e.w;

        if (t1 == t2) {
            bg[lst] = bg[t1];
            en[lst] = en[t1];
            isbam[lst] = false;
        } else {
            int ar[2][2] = {{bg[t1], en[t1]}, {bg[t2], en[t2]}}; 
            
            bool flag = true; 
            for (int bit_0 = 0; bit_0 < 2 && flag; bit_0++) {
                for (int bit_1 = 0; bit_1 < 2; bit_1++) {
                    if (e.u == ar[0][bit_0] && e.v == ar[1][bit_1]) {
                        bg[lst] = ar[0][!bit_0];
                        en[lst] = ar[1][!bit_1];
                        flag = false;
                        break;
                    }
                    if (e.v == ar[0][bit_0] && e.u == ar[1][bit_1]) {
                        bg[lst] = ar[0][!bit_0];
                        en[lst] = ar[1][!bit_1];
                        flag = false;
                        break;
                    }
                } 
            }
            if (flag) 
                isbam[lst] = false;
            else 
                isbam[lst] = (isbam[t1] & isbam[t2]);
        }
    }
    par[lst][0] = lst;
    for (int i = lst; i >= 0; i--) {
        for (int k = 1; k < 18; k++) {
            par[i][k] = par[ par[i][k - 1] ][k - 1];
        }
        if (par[i][0] != i)
            g[par[i][0]].push_back(i);
    }

    dfs(lst);
}

int getMinimumFuelCapacity(int X, int Y) {
    for (int i = 17; i >= 0; i--) {
        if (!up(par[X][i], Y) || isbam[par[X][i]])
            X = par[X][i];
    }
    if (up(par[X][0], Y) && !isbam[par[X][0]]) {
        X = par[X][0];
        return cap[X];
    }
    return -1;
}

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10584 KB Output is correct
2 Correct 2 ms 10588 KB Output is correct
3 Correct 2 ms 10588 KB Output is correct
4 Correct 3 ms 10588 KB Output is correct
5 Correct 2 ms 10716 KB Output is correct
6 Correct 2 ms 10588 KB Output is correct
7 Correct 2 ms 10588 KB Output is correct
8 Correct 3 ms 10760 KB Output is correct
9 Runtime error 49 ms 47268 KB Execution killed with signal 11
10 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10584 KB Output is correct
2 Correct 2 ms 10588 KB Output is correct
3 Runtime error 84 ms 57288 KB Execution killed with signal 11
4 Halted 0 ms 0 KB -

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10584 KB Output is correct
2 Correct 2 ms 10588 KB Output is correct
3 Correct 2 ms 10588 KB Output is correct
4 Correct 3 ms 10588 KB Output is correct
5 Correct 2 ms 10716 KB Output is correct
6 Correct 2 ms 10588 KB Output is correct
7 Correct 2 ms 10588 KB Output is correct
8 Correct 3 ms 10760 KB Output is correct
9 Correct 2 ms 10584 KB Output is correct
10 Correct 2 ms 10588 KB Output is correct
11 Correct 2 ms 10588 KB Output is correct
12 Correct 2 ms 10752 KB Output is correct
13 Correct 2 ms 10588 KB Output is correct
14 Correct 2 ms 10588 KB Output is correct
15 Correct 3 ms 10840 KB Output is correct
16 Correct 2 ms 10588 KB Output is correct
17 Correct 2 ms 10588 KB Output is correct
18 Correct 2 ms 10588 KB Output is correct
19 Correct 2 ms 10588 KB Output is correct
20 Correct 2 ms 10588 KB Output is correct
21 Correct 2 ms 10588 KB Output is correct
22 Correct 2 ms 10844 KB Output is correct
23 Correct 2 ms 10588 KB Output is correct
24 Correct 3 ms 10676 KB Output is correct
25 Correct 3 ms 10840 KB Output is correct
26 Correct 3 ms 10840 KB Output is correct
27 Correct 2 ms 10740 KB Output is correct
28 Correct 3 ms 10844 KB Output is correct

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10584 KB Output is correct
2 Correct 2 ms 10584 KB Output is correct
3 Correct 2 ms 10588 KB Output is correct
4 Correct 2 ms 10588 KB Output is correct
5 Correct 3 ms 10588 KB Output is correct
6 Correct 2 ms 10716 KB Output is correct
7 Correct 2 ms 10588 KB Output is correct
8 Correct 2 ms 10588 KB Output is correct
9 Correct 3 ms 10760 KB Output is correct
10 Runtime error 49 ms 47268 KB Execution killed with signal 11
11 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10584 KB Output is correct
2 Correct 2 ms 10588 KB Output is correct
3 Correct 2 ms 10588 KB Output is correct
4 Correct 3 ms 10588 KB Output is correct
5 Correct 2 ms 10716 KB Output is correct
6 Correct 2 ms 10588 KB Output is correct
7 Correct 2 ms 10588 KB Output is correct
8 Correct 3 ms 10760 KB Output is correct
9 Runtime error 49 ms 47268 KB Execution killed with signal 11
10 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10584 KB Output is correct
2 Correct 2 ms 10584 KB Output is correct
3 Correct 2 ms 10588 KB Output is correct
4 Correct 2 ms 10588 KB Output is correct
5 Correct 3 ms 10588 KB Output is correct
6 Correct 2 ms 10716 KB Output is correct
7 Correct 2 ms 10588 KB Output is correct
8 Correct 2 ms 10588 KB Output is correct
9 Correct 3 ms 10760 KB Output is correct
10 Runtime error 49 ms 47268 KB Execution killed with signal 11
11 Halted 0 ms 0 KB -