제출 #740090

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
740090		becaido	자매 도시 (APIO20_swap)	C++17	100 / 100	540 ms	331872 KiB

swap

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx,popcnt,sse4,abm")
#include <bits/stdc++.h>
using namespace std;

#ifndef WAIMAI
#include "swap.h"
#endif

#ifdef WAIMAI
#define debug(HEHE...) cout << "[" << #HEHE << "] : ", dout(HEHE)
void dout() {cout << '\n';}
template<typename T, typename...U>
void dout(T t, U...u) {cout << t << (sizeof...(u) ? ", " : ""), dout(u...);}
#else
#define debug(...) 7122
#endif

#define ll long long
#define Waimai ios::sync_with_stdio(false), cin.tie(0)
#define FOR(x,a,b) for (int x = a, I = b; x <= I; x++)
#define pb emplace_back
#define F first
#define S second

const int SIZE = 4e5 + 5;
const int H = __lg(SIZE);

int n, m;
int val[SIZE];
array<int, 3> e[SIZE];
vector<int> adj[SIZE];

struct DSU {
    int sz, to[SIZE];
    deque<int> v[SIZE];
    void init() {
        sz = n;
        iota(to + 1, to + n + m + 1, 1);
        FOR (i, 1, n) v[i].pb(i);
    }
    int dsu(int x) {
        return x == to[x] ? x : (to[x] = dsu(to[x]));
    }
    void Merge(int a, int b, int w) {
        debug("merge", a, b, w);
        int da = dsu(a), db = dsu(b);
        if (da == db) {
            debug("b0");
            if (v[da].size() == 0) return;
            sz++;
            val[sz] = w;
            to[da] = sz;
            for (int x : v[da]) adj[sz].pb(x);
            v[da].clear();
            return;
        }
        if (v[db].size() == 0 || (b != v[db][0] && b != v[db].back())) swap(a, b), swap(da, db);
        if (v[da].size() == 0) {
            debug("b1");
            sz++;
            val[sz] = w;
            adj[sz].pb(da), to[da] = to[db] = sz;
            if (v[db].size() == 0) adj[sz].pb(db);
            else {
                for (int x : v[db]) adj[sz].pb(x);
                v[db].clear();
            }
            return;
        }
        if (a != v[da][0] && a != v[da].back()) {
            debug("b2");
            sz++;
            val[sz] = w;
            to[da] = to[db] = sz;
            for (int x : v[da]) adj[sz].pb(x);
            v[da].clear();
            if (v[db].size() == 0) adj[sz].pb(db);
            else {
                for (int x : v[db]) adj[sz].pb(x);
                v[db].clear();
            }
            return;
        }
        debug("b3");
        if (v[da].size() < v[db].size()) {
            swap(a, b);
            swap(da, db);
        }
        if (b == v[db][0]) reverse(v[db].begin(), v[db].end());
        if (a == v[da][0]) while (v[db].size()) v[da].emplace_front(v[db].back()), v[db].pop_back();
        else while (v[db].size()) v[da].pb(v[db].back()), v[db].pop_back();
        to[db] = da;
    }
} dsu;

int h[SIZE], to[SIZE][H + 1];
void dfs(int pos) {
    for (int np : adj[pos]) {
        h[np] = h[pos] + 1;
        to[np][0] = pos;
        dfs(np);
    }
}
int jump(int pos, int k) {
    int cnt = 0;
    while (k) {
        if (k & 1) pos = to[pos][cnt];
        cnt++;
        k >>= 1;
    }
    return pos;
}
int lca(int a, int b) {
    if (h[a] < h[b]) swap(a, b);
    a = jump(a, h[a] - h[b]);
    if (a == b) return a;
    for (int i = H; i >= 0; i--) if (to[a][i] != to[b][i]) {
        a = to[a][i];
        b = to[b][i];
    }
    return to[a][0];
}

void init(int N, int M, vector<int> U, vector<int> V, vector<int> W) {
    n = N, m = M;
    FOR (i, 0, m - 1) e[i + 1] = {U[i] + 1, V[i] + 1, W[i]};
    sort(e + 1, e + m + 1, [](auto lhs, auto rhs) {
        return lhs[2] < rhs[2];
    });
    dsu.init();
    FOR (i, 1, m) {
        auto [a, b, w] = e[i];
        dsu.Merge(a, b, w);
    }
    FOR (i, 1, n + m) if (i == dsu.dsu(i)) h[i] = 1, dfs(i);
    FOR (j, 1, H) FOR (i, 1, n + m) to[i][j] = to[to[i][j - 1]][j - 1];
}

int getMinimumFuelCapacity(int a, int b) {
    a++, b++;
    if (dsu.dsu(a) != dsu.dsu(b) || dsu.v[dsu.dsu(a)].size() || dsu.v[dsu.dsu(b)].size()) return -1;
    return val[lca(a, b)];
}

/*
in1
5 6
0 1 4
0 2 4
1 2 1
1 3 2
1 4 10
2 3 3
3
1 2
2 4
0 1
out1
3
10
4
in2
3 2
0 1 5
0 2 5
1
1 2
out2
-1
*/

#ifdef WAIMAI
int main() {
  int N, M;
  assert(2 == scanf("%d %d", &N, &M));

  vector<int> U(M), V(M), W(M);
  for (int i = 0; i < M; ++i) {
    assert(3 == scanf("%d %d %d", &U[i], &V[i], &W[i]));
  }

  int Q;
  assert(1 == scanf("%d", &Q));

  vector<int> X(Q), Y(Q);
  for (int i = 0; i < Q; ++i) {
    assert(2 == scanf("%d %d", &X[i], &Y[i]));
  }

  init(N, M, U, V, W);

  vector<int> minimum_fuel_capacities(Q);
  for (int i = 0; i < Q; ++i) {
    minimum_fuel_capacities[i] = getMinimumFuelCapacity(X[i], Y[i]);
  }

  for (int i = 0; i < Q; ++i) {
    printf("%d\n", minimum_fuel_capacities[i]);
  }

  return 0;
}
#endif

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

swap.cpp: In member function 'void DSU::Merge(int, int, int)':
swap.cpp:16:20: warning: statement has no effect [-Wunused-value]
   16 | #define debug(...) 7122
      |                    ^~~~
swap.cpp:46:9: note: in expansion of macro 'debug'
   46 |         debug("merge", a, b, w);
      |         ^~~~~
swap.cpp:16:20: warning: statement has no effect [-Wunused-value]
   16 | #define debug(...) 7122
      |                    ^~~~
swap.cpp:49:13: note: in expansion of macro 'debug'
   49 |             debug("b0");
      |             ^~~~~
swap.cpp:16:20: warning: statement has no effect [-Wunused-value]
   16 | #define debug(...) 7122
      |                    ^~~~
swap.cpp:60:13: note: in expansion of macro 'debug'
   60 |             debug("b1");
      |             ^~~~~
swap.cpp:16:20: warning: statement has no effect [-Wunused-value]
   16 | #define debug(...) 7122
      |                    ^~~~
swap.cpp:72:13: note: in expansion of macro 'debug'
   72 |             debug("b2");
      |             ^~~~~
swap.cpp:16:20: warning: statement has no effect [-Wunused-value]
   16 | #define debug(...) 7122
      |                    ^~~~
swap.cpp:85:9: note: in expansion of macro 'debug'
   85 |         debug("b3");
      |         ^~~~~

• Subtask 1: 6 / 6
• Subtask 2: 7 / 7
• Subtask 3: 17 / 17
• Subtask 4: 20 / 20
• Subtask 5: 23 / 23
• Subtask 6: 27 / 27