Submission #976047

#	Time	Username	Problem	Language	Result	Execution time	Memory
976047		josanneo22	Swapping Cities (APIO20_swap)	C++17	100 / 100	304 ms	37540 KiB

swap

#include "swap.h"

#include <vector>
#include <bits/stdc++.h>
using namespace std;

const int nax = 300500, K = 22;
int N, M;
vector<pair<int, pair<int, int>>> edges;  

int fa[nax];
int child[nax][2];
int val[nax];
int dep[nax], sp[nax][K];
int st[nax], ed[nax];
bool chain[nax];

int find(int x) {
   if (x == fa[x]) return x;
   fa[x] = find(fa[x]);
   return fa[x];  
}

void dfs(int u, int f) {
   if (!u) return;
   // cout << "DFS : " << u << ' ' << f << '\n';
   dep[u] = dep[f] + 1; 
   sp[u][0] = f;
   for (int i = 1; i < K; i++) 
      sp[u][i] = sp[sp[u][i - 1]][i - 1];
   for (int t = 0; t < 2; t++) {
      int v = child[u][t];
      dfs(v, u);
   }
}

int lca(int X, int Y) {
   if (dep[Y] >= dep[X]) swap(X, Y);
   for (int i = K - 1; i >= 0; i--) if (dep[sp[X][i]] >= dep[Y]) X = sp[X][i];
   if (X == Y) return X;
   for (int i = K - 1; i >= 0; i--) if (sp[X][i] != sp[Y][i]) X = sp[X][i], Y = sp[Y][i];
   return sp[X][0];
}
int id;
void init(int _N, int _M, std::vector<int> _U, std::vector<int> _V, std::vector<int> _W) {
   N = _N; M = _M;
   id = N;
   for (int i = 0 ; i < M; i++) 
      edges.push_back(make_pair(_W[i], make_pair(_U[i] + 1, _V[i] + 1)));
   sort(edges.begin(), edges.end());
   for (int i = 0; i < nax; i++) fa[i] = i;
   for (int i = 1; i <= N; i++) {
      chain[i] = true;
      st[i] = ed[i] = i;
   }
   for (int i = 0; i < edges.size(); i++) {
      int w = edges[i].first;
      int u = edges[i].second.first;
      int v = edges[i].second.second;
      int A = find(u), B = find(v);
      // cout << A << ' ' << B << '\n';
      if (A == B) {
         if (chain[A]) {
            int g = ++id;
            fa[A] = g;
            val[g] = w;
            child[g][0] = A;
         }
         continue;
      }
      int g = ++id;
      fa[A] = g; fa[B] = g;
      val[g] = w;
      child[g][0] = A; child[g][1] = B;
      if (chain[A] && chain[B]) {
         // ...u, v...
         if (st[A] == v || ed[A] == v) swap(A, B);
         if (st[A] == u) swap(st[A], ed[A]);
         if (ed[B] == v) swap(st[B], ed[B]);
         if (ed[A] == u && st[B] == v) {
            chain[g] = true;
            st[g] = st[A];
            ed[g] = ed[B];
         }
      }
   }
   dfs(id, 0);
   // for (int i = 1; i <= 10; i++) cout << val[i] << ' ';
   //    cout << '\n';
}

int getMinimumFuelCapacity(int X, int Y) {
   X++; Y++;
   // cout << X << ' ' << Y << '\n';
   int l = lca(X, Y);
   // cout << "lca : " << l << '\n';
   if (!chain[l]) return val[l];
   for (int i = K - 1; i >= 0; i--) if (sp[l][i] && chain[sp[l][i]]) l = sp[l][i];
    if (l == id) return -1; 
    return val[sp[l][0]];
}

// #include "grader.cpp"

/*
要么是deg >= 3, 要么是cycle
考虑什么时候不能：链

我们可以直接维持kruskal重构树,
   让chain[i] = true/false
   u, v -> new node
   然后new node点权 = w
   那么答案就是
   在lca上倍增直到chain[i] = true为此
   然后 ans = cal[fa[lca]]
   判断chain[i] 可以用看u -> v是不是两个corner
*/

Compilation message (stderr)

swap.cpp: In function 'void init(int, int, std::vector<int>, std::vector<int>, std::vector<int>)':
swap.cpp:56:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   56 |    for (int i = 0; i < edges.size(); i++) {
      |                    ~~^~~~~~~~~~~~~~

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