제출 #568375

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
568375		pakhomovee	자매 도시 (APIO20_swap)	C++17	0 / 100	651 ms	49596 KiB

swap

#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);
}

컴파일 시 표준 에러 (stderr) 메시지

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
• Subtask 2: 0 / 7
• Subtask 3: 0 / 17
• Subtask 4: 0 / 20
• Subtask 5: 0 / 23
• Subtask 6: 0 / 27