oj.uz

Submission #571176

# Submission time Handle Problem Language Result Execution time Memory
571176 2022-06-01T11:55:41 Z Vanilla Swapping Cities (APIO20_swap) C++17
0 / 100
 31 ms 61312 KB 
#include "swap.h"
#include <bits/stdc++.h>
using namespace std;
const int maxn = 4e5 + 2;
int extra = 9;
const int lg = 25;
vector <int> ad [maxn];
int deg[maxn];
int dad [maxn];
int val [maxn];
vector <bool> line (maxn, 1);
vector <int> cmp[maxn];
vector <int> depth (maxn);
int up[maxn][lg];
 
void dfs (int u) {
    for (auto v: cmp[u]) {
        depth[v] = depth[u] + 1;
        up[v][0] = u;
        for (int i = 1; i < lg; i++){
            up[v][i] = up[up[v][i-1]][i-1];
        }
        dfs(v);
    }
}
 
int lca (int x, int y) {
    if (depth[x] < depth[y]) {
        swap(x, y);
    }
    int k = depth[x] - depth[y];
    for (int i = 0; i < lg; i++){
        if (k & (1 << i)) {
            x = up[x][i];
        }
    }
    if (x == y) return x;
    for (int i = lg - 1; i >= 0; i--) {
        if (up[x][i] != up[y][i]) {
            x = up[x][i];
            y = up[y][i];
        }
    }
    return up[x][0];
}
 

int get_dad (int x) {
  return (dad[x] == x ? x: get_dad(dad[x]));
}

void merge (int a, int b) {
  a = get_dad(a);
  b = get_dad(b);
  if (a == b) return;
  if (!line[a]) line[b] = 0;
  dad[a] = b;
  cmp[b].push_back(a);
}

void find (int u, vector <int> &nodes) {
  nodes.push_back(u);
  for (int v: cmp[u]) {
    find(v, nodes);
  }
}


struct edg {
  int x,y,cost;
};

bool comp (edg &a, edg &b) {
  return a.cost < b.cost;
}

void init(int n, int m, vector<int> u, vector<int> v, vector<int> w) {
  vector <edg> eg;
  for (int i = 0; i < maxn; i++){
    dad[i] = i;
    for (int j = 0; j < lg; j++){
      up[i][j] = maxn - 1;
    }
  }
  for (int i = 0; i < m; i++){
    eg.push_back({u[i], v[i], w[i]});
  }
  sort(eg.begin(), eg.end(), comp);
  for (auto &[u,v,cost]: eg) {
    // if (u == 1 && v == 4) break;
    int p1 = get_dad(u);
    int p2 = get_dad(v);
    // cout << u << " " << v << " " << p1 << " " << p2 << " ";
    if (p1 == p2) { 
      if (line[p1]) {
        vector <int> nodes;
        find(p1, nodes);
        int node = ++extra;
        for (int i: nodes) {
          dad[i] = node;
          cmp[node].push_back(i);
        }
        line[p1] = 0;
        val[node] = cost;
      }
    }
    else {
      deg[u]++;
      deg[v]++;
      if (deg[u] >= 3 || deg[v] >= 3) {
        int node = ++extra;
        line[node] = 0;
        merge(p1, node);
        merge(p2, node);
        val[node] = cost;
      }
      else merge(u,v);
    }
  }
  // for (int i = 0; i < 15; i++){
  //   cout << i << " " << val[i] << "\n";
  // }
  // for (int i = 0; i < 15; i++){
  //   cout << i << ": ";
  //   for (int j: cmp[i]) {
  //     cout << j << " ";
  //   }
  //   cout << "\n";
  // }
  // for (int i = 0; i < 15; i++){
  //   cout << i << " " << dad[i] << "\n";
  // }
  dfs(extra);

}

int getMinimumFuelCapacity(int x, int y) {
  return val[lca(x,y)];
}

Subtask #1
0 / 6.0

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

Subtask #2
0 / 7.0

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

Subtask #3
0 / 17.0

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

Subtask #4
0 / 20.0

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

Subtask #5
0 / 23.0

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

Subtask #6
0 / 27.0

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