oj.uz

Submission #683238

# Submission time Handle Problem Language Result Execution time Memory
683238 2023-01-18T02:34:28 Z Nursik Swapping Cities (APIO20_swap) C++14
0 / 100
 12 ms 24020 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 timer, p[maxn], sz[maxn], is[maxn], lst[maxn], deg[maxn], tin[maxn], tout[maxn], up[20][maxn], ans[maxn];
vector<pair<int, pair<int, int>>> kektor;
vector<int> g[maxn];
int get(int v){
    if (v == p[v])
        return v;
    return p[v] = get(p[v]);
}
bool upper(int a, int b){
    return (tin[a] <= tin[b] && tout[a] >= tout[b]);
}
int lca(int a, int b){
    if (upper(a, b))
        return a;
    if (upper(b, a))
        return b;
    for (int i = 19; i >= 0; --i){
        if (up[i][a] > 0 && !upper(up[i][a], b)){
            a = up[i][a];
        }
    }
    return up[0][a];
}
void dfs(int v, int par, int last){
    up[0][v] = par, tin[v] = ++timer;
    for (int i = 1; i <= 19; ++i){
        up[i][v] = up[i - 1][up[i - 1][v]];
    }
    if (is[v] > 0){
        last = v;
    }
    ans[v] = last;
    for (auto to : g[v]){
        if (to != par){
            dfs(to, v, last);
        }
    }
    tout[v] = ++timer;
}
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];
        kektor.pb(mp(w[i], mp(x, y)));
    }
    sort(kektor.begin(), kektor.end());
    for (int i = 0; i < n + m; ++i){
        p[i] = i, sz[i] = 1, is[i] = 0;
    }
    int uk = n;
    for (int i = 0; i < m; ++i){
        pair<int, pair<int, int>> cur = kektor[i];
        int cost = cur.f, x = cur.s.f, y = cur.s.s;
        int r = get(x), r2 = get(y);
        deg[x] += 1, deg[y] += 1;
        if (r == r2){
            g[uk].pb(r);
            g[r].pb(uk);
            lst[uk] = cost;
            is[uk] |= 1;
            p[r] = uk;
            uk += 1;
        }
        else{
            g[uk].pb(r);
            g[r].pb(uk);
            g[uk].pb(r2);
            g[r2].pb(uk);
          //  cout << uk << " " << r << '\n';
          //  cout << uk << " " << r2 << '\n';
            lst[uk] = cost;
            is[uk] |= (is[r] | is[r2]);
            is[uk] |= (deg[x] >= 3);
            is[uk] |= (deg[y] >= 3);
            p[r] = uk, p[r2] = uk;
            uk += 1;
        }
    }
    dfs(n + m - 1, 0, -1);
}
int getMinimumFuelCapacity(int x, int y) {
    int lc = lca(x, y);
    if (ans[lc] == -1)
        return -1;
    return lst[ans[lc]];
}

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 12 ms 24020 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 12 ms 24020 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 12 ms 24020 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 12 ms 24020 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 12 ms 24020 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Incorrect 12 ms 24020 KB Output isn't correct
2 Halted 0 ms 0 KB -