oj.uz

Submission #568373

# Submission time Handle Problem Language Result Execution time Memory
568373 2022-05-25T09:53:13 Z pakhomovee Swapping Cities (APIO20_swap) C++17
0 / 100
 662 ms 52292 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];
        }
    }
    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 'void dfs(int, int, int, std::pair<int, int>)':
swap.cpp:138: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]
  138 |         while (ptr < gg[p].size() && (gg[p][ptr] == make_pair(v, q) || gg[p][ptr] == pr)) ++ptr;
      |                ~~~~^~~~~~~~~~~~~~
swap.cpp:139: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]
  139 |         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 4 ms 5972 KB Output is correct
4 Correct 5 ms 6228 KB Output is correct
5 Correct 5 ms 6424 KB Output is correct
6 Correct 5 ms 6428 KB Output is correct
7 Correct 5 ms 6484 KB Output is correct
8 Correct 5 ms 6484 KB Output is correct
9 Correct 223 ms 38504 KB Output is correct
10 Correct 261 ms 46992 KB Output is correct
11 Correct 274 ms 45824 KB Output is correct
12 Correct 265 ms 48292 KB Output is correct
13 Correct 278 ms 50004 KB Output is correct
14 Correct 262 ms 38064 KB Output is correct
15 Correct 662 ms 49404 KB Output is correct
16 Correct 616 ms 46784 KB Output is correct
17 Correct 637 ms 52292 KB Output is correct
18 Correct 642 ms 50900 KB Output is correct
19 Incorrect 175 ms 16952 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 281 ms 41788 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 4 ms 5972 KB Output is correct
4 Correct 5 ms 6228 KB Output is correct
5 Correct 5 ms 6424 KB Output is correct
6 Correct 5 ms 6428 KB Output is correct
7 Correct 5 ms 6484 KB Output is correct
8 Correct 5 ms 6484 KB Output is correct
9 Incorrect 4 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 4 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 4 ms 5972 KB Output is correct
4 Correct 5 ms 6228 KB Output is correct
5 Correct 5 ms 6424 KB Output is correct
6 Correct 5 ms 6428 KB Output is correct
7 Correct 5 ms 6484 KB Output is correct
8 Correct 5 ms 6484 KB Output is correct
9 Correct 223 ms 38504 KB Output is correct
10 Correct 261 ms 46992 KB Output is correct
11 Correct 274 ms 45824 KB Output is correct
12 Correct 265 ms 48292 KB Output is correct
13 Correct 278 ms 50004 KB Output is correct
14 Correct 262 ms 38064 KB Output is correct
15 Correct 662 ms 49404 KB Output is correct
16 Correct 616 ms 46784 KB Output is correct
17 Correct 637 ms 52292 KB Output is correct
18 Correct 642 ms 50900 KB Output is correct
19 Incorrect 281 ms 41788 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

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