oj.uz

Submission #568375

# Submission time Handle Problem Language Result Execution time Memory
568375 2022-05-25T10:04:31 Z pakhomovee Swapping Cities (APIO20_swap) C++17
0 / 100
 651 ms 49596 KB 
#include "swap.h"
#include <iostream>
#include <vector>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <deque>
#include <queue>
#include <algorithm>
#include <cassert>
#include <numeric>

using namespace std;

#define all(x) x.begin(), x.end()

const int maxn = 1e5;
const int inf = 2e9;

struct dsu {
    int p[maxn];
    int sz[maxn];
    
    void init(int n) {
        iota(p, p + n, 0);
        fill(sz, sz + n, 1);
    }
    
    int c(int v) {
        return (v == p[v] ? v : p[v] = c(p[v]));
    }
    
    int szz(int v) {
        return sz[c(v)];
    }
    
    void unite(int u, int v) {
        u = c(u);
        v = c(v);
        if (u == v) {
            return;
        }
        p[u] = v;
        sz[v] += sz[u];
    }
};

vector<pair<int, pair<int, int>>> e;
int n;
vector<pair<int, int>> g[maxn];
vector<pair<int, int>> gg[maxn];
int timer = 0;
int tin[maxn];
int tout[maxn];
int up[20][maxn];
int cup[20][maxn];
int mp[20][maxn];
int cyc[20][maxn];
int cycleCost[maxn];
int minE[maxn];
vector<int> w;

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

int len(int u, int v) {
    int ans = inf;
    for (int i = 19; i >= 0; --i) {
        if (!isParent(up[i][u], v)) {
            ans = min(ans, cup[i][u]);
            u = up[i][u];
        }
    }
    for (int i = 19; i >= 0; --i) {
        if (!isParent(up[i][v], u)) {
            ans = min(ans, cup[i][v]);
            v = up[i][v];
        }
    }
    if (!isParent(u, v) && !isParent(v, u)) {
        int ptr = 0;
        int p = up[0][u];
        while (ptr < gg[p].size() && (gg[p][ptr].first == u || gg[p][ptr].first == v)) ++ptr;
        if (ptr < gg[p].size()) {
            ans = min(ans, w[gg[p][ptr].second]);
        }
    }
    return ans;
}

int go(int u, int v) {
    int ans = 0;
    for (int i = 19; i >= 0; --i) {
        if (!isParent(up[i][u], v)) {
            ans = max(ans, mp[i][u]);
            u = up[i][u];
        }
    }
    for (int i = 19; i >= 0; --i) {
        if (!isParent(up[i][v], u)) {
            ans = max(ans, mp[i][v]);
            v = up[i][v];
        }
    }
    int t = 0;
    if (!isParent(u, v)) {
        t = mp[0][u];
    }
    if (!isParent(v, u)) {
        t = max(t, mp[0][v]);
    }
    return max(ans, t);
}

int cost(int u, int v) {
    return inf;
    int ans = inf;
    for (int i = 19; i >= 0; --i) {
        if (!isParent(up[i][u], v)) {
            ans = min(ans, cyc[i][u]);
            u = up[i][u];
        }
    }
    for (int i = 19; i >= 0; --i) {
        if (!isParent(up[i][v], u)) {
            ans = min(ans, cyc[i][v]);
            v = up[i][v];
        }
    }
    return ans;
}

void dfs(int v, int p, int q, pair<int, int> pr) {
    up[0][v] = p;
    for (int i = 1; i < 20; ++i) {
        up[i][v] = up[i - 1][up[i - 1][v]];
    }
    for (int j = 0; j < 20; ++j) {
        cup[j][v] = inf;
        mp[j][v] = 0;
    }
    if (v > 0) {
        int ptr = 0;
        while (ptr < gg[p].size() && (gg[p][ptr] == make_pair(v, q) || gg[p][ptr] == pr)) ++ptr;
        if (ptr < gg[p].size()) {
            cup[0][v] = w[gg[p][ptr].second];
        }
        for (int j = 1; j < 20; ++j) {
            cup[j][v] = min(cup[j - 1][v], cup[j - 1][up[j - 1][v]]);
        }
    }
    if (q != -1) {
        mp[0][v] = w[q];
        for (int j = 1; j < 20; ++j) {
            mp[j][v] = max(mp[j - 1][v], mp[j - 1][up[j - 1][v]]);
        }
    }
    tin[v] = timer++;
    
    for (auto [u, w] : g[v]) {
        if (u != p) {
            dfs(u, v, w, { p, q });
        }
    }
    
    tout[v] = timer++;
}

bool cmp(pair<int, pair<int, int>> a, pair<int, pair<int, int>> b) {
    if (w[a.first] != w[b.first]) {
        return w[a.first] < w[b.first];
    }
    return a.second < b.second;
}

bool cmp1(pair<int, int> a, pair<int, int> b) {
    if (w[a.second] != w[b.second]) {
        return w[a.second] < w[b.second];
    }
    return a.first < b.first;
}

void init(int N, int M, std::vector<int> U, std::vector<int> V, std::vector<int> W) {
    n = N;
    w = W;
    for (int i = 0; i < M; ++i) {
        e.push_back({ i, { U[i], V[i] } });
        gg[U[i]].push_back({ V[i], i });
        gg[V[i]].push_back({ U[i], i });
    }
    for (int i = 0; i < N; ++i) {
        sort(all(gg[i]), cmp1);
    }
    sort(all(e), cmp);
    dsu ds;
    ds.init(N);
    for (int i = 0; i < M; ++i) {
        auto [u, v] = e[i].second;
        if (ds.c(u) != ds.c(v)) {
            g[u].push_back({ v, e[i].first });
            g[v].push_back({ u, e[i].first });
            ds.unite(u, v);
        }
    }
    
    //  calc cycles
    
    dfs(0, 0, -1, { -1, - 1 });
}

int getMinimumFuelCapacity(int X, int Y) {
    //cout << "LEN: " << len(X, Y) << endl;
    int ans = max(go(X, Y), min(len(X, Y), cost(X, Y)));
    return (ans == inf ? -1 : ans);
}

Compilation message

swap.cpp: In function 'int len(int, int)':
swap.cpp:85:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   85 |         while (ptr < gg[p].size() && (gg[p][ptr].first == u || gg[p][ptr].first == v)) ++ptr;
      |                ~~~~^~~~~~~~~~~~~~
swap.cpp:86:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   86 |         if (ptr < gg[p].size()) {
      |             ~~~~^~~~~~~~~~~~~~
swap.cpp: In function 'void dfs(int, int, int, std::pair<int, int>)':
swap.cpp:146:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  146 |         while (ptr < gg[p].size() && (gg[p][ptr] == make_pair(v, q) || gg[p][ptr] == pr)) ++ptr;
      |                ~~~~^~~~~~~~~~~~~~
swap.cpp:147:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  147 |         if (ptr < gg[p].size()) {
      |             ~~~~^~~~~~~~~~~~~~

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5972 KB Output is correct
2 Correct 3 ms 5972 KB Output is correct
3 Correct 3 ms 6076 KB Output is correct
4 Correct 3 ms 6228 KB Output is correct
5 Correct 4 ms 6356 KB Output is correct
6 Correct 5 ms 6356 KB Output is correct
7 Correct 4 ms 6356 KB Output is correct
8 Correct 4 ms 6484 KB Output is correct
9 Correct 179 ms 36772 KB Output is correct
10 Correct 227 ms 44916 KB Output is correct
11 Correct 227 ms 43848 KB Output is correct
12 Correct 242 ms 46252 KB Output is correct
13 Correct 231 ms 47836 KB Output is correct
14 Correct 214 ms 36196 KB Output is correct
15 Correct 582 ms 46788 KB Output is correct
16 Correct 575 ms 44088 KB Output is correct
17 Correct 651 ms 49596 KB Output is correct
18 Correct 586 ms 48220 KB Output is correct
19 Incorrect 156 ms 15012 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5972 KB Output is correct
2 Correct 3 ms 5972 KB Output is correct
3 Incorrect 290 ms 43180 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5972 KB Output is correct
2 Correct 3 ms 5972 KB Output is correct
3 Correct 3 ms 6076 KB Output is correct
4 Correct 3 ms 6228 KB Output is correct
5 Correct 4 ms 6356 KB Output is correct
6 Correct 5 ms 6356 KB Output is correct
7 Correct 4 ms 6356 KB Output is correct
8 Correct 4 ms 6484 KB Output is correct
9 Incorrect 3 ms 5972 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

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

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5972 KB Output is correct
2 Correct 3 ms 5972 KB Output is correct
3 Correct 3 ms 6076 KB Output is correct
4 Correct 3 ms 6228 KB Output is correct
5 Correct 4 ms 6356 KB Output is correct
6 Correct 5 ms 6356 KB Output is correct
7 Correct 4 ms 6356 KB Output is correct
8 Correct 4 ms 6484 KB Output is correct
9 Correct 179 ms 36772 KB Output is correct
10 Correct 227 ms 44916 KB Output is correct
11 Correct 227 ms 43848 KB Output is correct
12 Correct 242 ms 46252 KB Output is correct
13 Correct 231 ms 47836 KB Output is correct
14 Correct 214 ms 36196 KB Output is correct
15 Correct 582 ms 46788 KB Output is correct
16 Correct 575 ms 44088 KB Output is correct
17 Correct 651 ms 49596 KB Output is correct
18 Correct 586 ms 48220 KB Output is correct
19 Incorrect 290 ms 43180 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

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