oj.uz

Submission #571142

# Submission time Handle Problem Language Result Execution time Memory
571142 2022-06-01T10:14:19 Z SlavicG Swapping Cities (APIO20_swap) C++17
0 / 100
 325 ms 69756 KB 
#include "bits/stdc++.h"
using namespace std;
 
#define ll long long
 
#define       forn(i,n)              for(int i=0;i<n;i++)
#define          all(v)              v.begin(), v.end()
#define         rall(v)              v.rbegin(),v.rend()
 
#define            pb                push_back
#define          sz(a)               (int)a.size()

const int N = 4e5 + 10, K = 25;
vector<int> adj[N], g[N];
int val[N], degree[N], depth[N], jump[N][K], id, n;
bool vis[N], good;


struct DSU {
    vector<int> par;
    DSU() {
        par.assign(N, 0);
        forn(i, N) par[i] = i;
    }
    int get(int a) {
        return par[a] = (par[a] == a ? a : get(par[a]));
    }
    void uni(int a, int b) {
        par[a] = b;
    }
};
vector<int> component;

void get_component(int u) {
    vis[u] = true;
    component.pb(u);
    for(int v: g[u]) {
        if(!vis[v]) get_component(v);
    }
}

void dfs(int u, int par) {
    jump[u][0] = par;
    for(int v: adj[u]) {
        if(v == par) continue;
        depth[v] = depth[u] + 1;
        dfs(v, u);
    }
}

int LCA(int u, int v) {
    if(depth[u] < depth[v]) swap(u, v);

    for(int j = K - 1; j >= 0; --j) {
        if(depth[jump[u][j]] > depth[v]) {
            u = jump[u][j];
        }
    }
    if(u == v) return u;
    for(int j = K - 1; j >= 0; --j) {
        if(jump[u][j] != jump[v][j]) {
            u = jump[u][j], v = jump[v][j];
        }
    }
    return jump[u][0];
}

void init(int N, int m, vector<int> U, vector<int> V, vector<int> W) {
    n = N;
    id = n;

    vector<array<int, 3>> edges;
    DSU d;
    DSU connect;
    for(int i = 0; i < m; ++i) {
        edges.pb({W[i], U[i], V[i]});
    }
    sort(all(edges));
    
    for(auto x: edges) {
        int u = x[1], v = x[2], w = x[0];

        if(d.get(u) == d.get(v)) continue;
        if(d.get(u) == u) swap(u, v);

        if(d.get(u) != u && d.get(v) != v) {
            adj[id].pb(d.get(u));
            adj[id].pb(d.get(v));
            d.uni(u, id);
            d.uni(v, id);
            val[id] = w;
            ++id;
        } else if(d.get(u) != u) {
            component.clear();
            get_component(v);
            for(auto x: component) {
                adj[id].pb(x);
                d.uni(x, id);
            }
            ++id;

            adj[id].pb(d.get(u));
            adj[id].pb(d.get(v));
            d.uni(u, id);
            d.uni(v, id);
            val[id] = w;
            ++id;
        } else {
            g[u].pb(v);
            g[v].pb(u);
            ++degree[u];
            ++degree[v];
            if(connect.get(u) == connect.get(v) || degree[u] > 2 || degree[v] > 2) {
                component.clear();
                get_component(u);
                good = true;
                for(auto x: component) {
                    d.uni(x, id);
                    adj[id].pb(x);
                }
                
                val[id] = w;
                ++id;
            } else{
                connect.uni(u, v);
            }

        }
    }
    
    dfs(id - 1, id - 1);
    for(int k = 1; k < K; ++k) {
        for(int i = 0; i < N; ++i) {
            jump[i][k] = id - 1;
        }
    }

    for(int k = 1; k < K; ++k) {
        for(int i = 0; i < N; ++i) {
            jump[i][k] = jump[jump[i][k - 1]][k - 1];
        }
    }

    
}

int getMinimumFuelCapacity(int u, int v) {
    if(!good) return -1;
    return val[LCA(u, v)];
}
/*
void solve() {  
    int NN, m; cin >> NN >> m;
    vector<int> a(m), b(m), c(m);
    forn(i, m) cin >> a[i];
    forn(i, m) cin >> b[i];
    forn(i, m) cin >> c[i];
    init(NN, m, a, b, c);
    cout << getMinimumFuelCapacity(1, 2) << "\n";
    cout << getMinimumFuelCapacity(2, 4) << "\n";
    cout << getMinimumFuelCapacity(0, 1) << "\n";
    
}   
     
int32_t main() {
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int t = 1;
    //cin >> t;
    while(t--) {
        solve();
    }
}
*/

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 22228 KB Output is correct
2 Correct 12 ms 22228 KB Output is correct
3 Correct 15 ms 22188 KB Output is correct
4 Correct 16 ms 22292 KB Output is correct
5 Correct 13 ms 22356 KB Output is correct
6 Correct 12 ms 22356 KB Output is correct
7 Correct 13 ms 22356 KB Output is correct
8 Correct 13 ms 22356 KB Output is correct
9 Correct 103 ms 36612 KB Output is correct
10 Correct 138 ms 39488 KB Output is correct
11 Correct 146 ms 39424 KB Output is correct
12 Correct 171 ms 40152 KB Output is correct
13 Correct 128 ms 40332 KB Output is correct
14 Correct 123 ms 36624 KB Output is correct
15 Correct 234 ms 41304 KB Output is correct
16 Correct 201 ms 40740 KB Output is correct
17 Correct 205 ms 41808 KB Output is correct
18 Correct 209 ms 41868 KB Output is correct
19 Incorrect 78 ms 27272 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 22228 KB Output is correct
2 Correct 12 ms 22228 KB Output is correct
3 Incorrect 325 ms 69756 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 22228 KB Output is correct
2 Correct 12 ms 22228 KB Output is correct
3 Correct 15 ms 22188 KB Output is correct
4 Correct 16 ms 22292 KB Output is correct
5 Correct 13 ms 22356 KB Output is correct
6 Correct 12 ms 22356 KB Output is correct
7 Correct 13 ms 22356 KB Output is correct
8 Correct 13 ms 22356 KB Output is correct
9 Correct 17 ms 22160 KB Output is correct
10 Incorrect 13 ms 22452 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 22160 KB Output is correct
2 Correct 12 ms 22228 KB Output is correct
3 Correct 12 ms 22228 KB Output is correct
4 Correct 15 ms 22188 KB Output is correct
5 Correct 16 ms 22292 KB Output is correct
6 Correct 13 ms 22356 KB Output is correct
7 Correct 12 ms 22356 KB Output is correct
8 Correct 13 ms 22356 KB Output is correct
9 Correct 13 ms 22356 KB Output is correct
10 Correct 103 ms 36612 KB Output is correct
11 Correct 138 ms 39488 KB Output is correct
12 Correct 146 ms 39424 KB Output is correct
13 Correct 171 ms 40152 KB Output is correct
14 Correct 128 ms 40332 KB Output is correct
15 Incorrect 13 ms 22452 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 22228 KB Output is correct
2 Correct 12 ms 22228 KB Output is correct
3 Correct 15 ms 22188 KB Output is correct
4 Correct 16 ms 22292 KB Output is correct
5 Correct 13 ms 22356 KB Output is correct
6 Correct 12 ms 22356 KB Output is correct
7 Correct 13 ms 22356 KB Output is correct
8 Correct 13 ms 22356 KB Output is correct
9 Correct 103 ms 36612 KB Output is correct
10 Correct 138 ms 39488 KB Output is correct
11 Correct 146 ms 39424 KB Output is correct
12 Correct 171 ms 40152 KB Output is correct
13 Correct 128 ms 40332 KB Output is correct
14 Correct 123 ms 36624 KB Output is correct
15 Correct 234 ms 41304 KB Output is correct
16 Correct 201 ms 40740 KB Output is correct
17 Correct 205 ms 41808 KB Output is correct
18 Correct 209 ms 41868 KB Output is correct
19 Incorrect 325 ms 69756 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 22160 KB Output is correct
2 Correct 12 ms 22228 KB Output is correct
3 Correct 12 ms 22228 KB Output is correct
4 Correct 15 ms 22188 KB Output is correct
5 Correct 16 ms 22292 KB Output is correct
6 Correct 13 ms 22356 KB Output is correct
7 Correct 12 ms 22356 KB Output is correct
8 Correct 13 ms 22356 KB Output is correct
9 Correct 13 ms 22356 KB Output is correct
10 Correct 103 ms 36612 KB Output is correct
11 Correct 138 ms 39488 KB Output is correct
12 Correct 146 ms 39424 KB Output is correct
13 Correct 171 ms 40152 KB Output is correct
14 Correct 128 ms 40332 KB Output is correct
15 Correct 123 ms 36624 KB Output is correct
16 Correct 234 ms 41304 KB Output is correct
17 Correct 201 ms 40740 KB Output is correct
18 Correct 205 ms 41808 KB Output is correct
19 Correct 209 ms 41868 KB Output is correct
20 Incorrect 325 ms 69756 KB Output isn't correct
21 Halted 0 ms 0 KB -