oj.uz

Submission #571178

# Submission time Handle Problem Language Result Execution time Memory
571178 2022-06-01T12:01:58 Z Vanilla Swapping Cities (APIO20_swap) C++17
0 / 100
 2000 ms 68892 KB 
#include "swap.h"
#include <bits/stdc++.h>
using namespace std;
const int maxn = 4e5 + 2;
int extra = 2e5 + 1;
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 dg[maxn];
int up[maxn][lg];
bool bad1 = 1, bad2 = 1;
 
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++){
    dg[u[i]]++;
    dg[v[i]]++;
    eg.push_back({u[i], v[i], w[i]});
  }
  for (int i = 0; i < n; i++){
    if (dg[i] > 2) bad1 = 0;
    if (dg[i] != 2) bad2 = 0;
  }
  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) {
  if (bad1 || bad2) return -1;
  return val[lca(x,y)];
}

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 61344 KB Output is correct
2 Correct 28 ms 61372 KB Output is correct
3 Correct 29 ms 61400 KB Output is correct
4 Correct 31 ms 61376 KB Output is correct
5 Correct 29 ms 61472 KB Output is correct
6 Correct 29 ms 61452 KB Output is correct
7 Correct 38 ms 61432 KB Output is correct
8 Correct 43 ms 61432 KB Output is correct
9 Correct 76 ms 66100 KB Output is correct
10 Correct 80 ms 67036 KB Output is correct
11 Correct 82 ms 67000 KB Output is correct
12 Correct 111 ms 67328 KB Output is correct
13 Correct 94 ms 67224 KB Output is correct
14 Correct 78 ms 66188 KB Output is correct
15 Correct 141 ms 68700 KB Output is correct
16 Correct 162 ms 68452 KB Output is correct
17 Correct 184 ms 68856 KB Output is correct
18 Correct 141 ms 68892 KB Output is correct
19 Incorrect 118 ms 64652 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 61344 KB Output is correct
2 Correct 28 ms 61372 KB Output is correct
3 Execution timed out 2075 ms 68440 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 61344 KB Output is correct
2 Correct 28 ms 61372 KB Output is correct
3 Correct 29 ms 61400 KB Output is correct
4 Correct 31 ms 61376 KB Output is correct
5 Correct 29 ms 61472 KB Output is correct
6 Correct 29 ms 61452 KB Output is correct
7 Correct 38 ms 61432 KB Output is correct
8 Correct 43 ms 61432 KB Output is correct
9 Correct 29 ms 61436 KB Output is correct
10 Correct 29 ms 61408 KB Output is correct
11 Incorrect 29 ms 61380 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 61436 KB Output is correct
2 Correct 28 ms 61344 KB Output is correct
3 Correct 28 ms 61372 KB Output is correct
4 Correct 29 ms 61400 KB Output is correct
5 Correct 31 ms 61376 KB Output is correct
6 Correct 29 ms 61472 KB Output is correct
7 Correct 29 ms 61452 KB Output is correct
8 Correct 38 ms 61432 KB Output is correct
9 Correct 43 ms 61432 KB Output is correct
10 Correct 76 ms 66100 KB Output is correct
11 Correct 80 ms 67036 KB Output is correct
12 Correct 82 ms 67000 KB Output is correct
13 Correct 111 ms 67328 KB Output is correct
14 Correct 94 ms 67224 KB Output is correct
15 Correct 29 ms 61408 KB Output is correct
16 Incorrect 29 ms 61380 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 61344 KB Output is correct
2 Correct 28 ms 61372 KB Output is correct
3 Correct 29 ms 61400 KB Output is correct
4 Correct 31 ms 61376 KB Output is correct
5 Correct 29 ms 61472 KB Output is correct
6 Correct 29 ms 61452 KB Output is correct
7 Correct 38 ms 61432 KB Output is correct
8 Correct 43 ms 61432 KB Output is correct
9 Correct 76 ms 66100 KB Output is correct
10 Correct 80 ms 67036 KB Output is correct
11 Correct 82 ms 67000 KB Output is correct
12 Correct 111 ms 67328 KB Output is correct
13 Correct 94 ms 67224 KB Output is correct
14 Correct 78 ms 66188 KB Output is correct
15 Correct 141 ms 68700 KB Output is correct
16 Correct 162 ms 68452 KB Output is correct
17 Correct 184 ms 68856 KB Output is correct
18 Correct 141 ms 68892 KB Output is correct
19 Execution timed out 2075 ms 68440 KB Time limit exceeded
20 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 61436 KB Output is correct
2 Correct 28 ms 61344 KB Output is correct
3 Correct 28 ms 61372 KB Output is correct
4 Correct 29 ms 61400 KB Output is correct
5 Correct 31 ms 61376 KB Output is correct
6 Correct 29 ms 61472 KB Output is correct
7 Correct 29 ms 61452 KB Output is correct
8 Correct 38 ms 61432 KB Output is correct
9 Correct 43 ms 61432 KB Output is correct
10 Correct 76 ms 66100 KB Output is correct
11 Correct 80 ms 67036 KB Output is correct
12 Correct 82 ms 67000 KB Output is correct
13 Correct 111 ms 67328 KB Output is correct
14 Correct 94 ms 67224 KB Output is correct
15 Correct 78 ms 66188 KB Output is correct
16 Correct 141 ms 68700 KB Output is correct
17 Correct 162 ms 68452 KB Output is correct
18 Correct 184 ms 68856 KB Output is correct
19 Correct 141 ms 68892 KB Output is correct
20 Execution timed out 2075 ms 68440 KB Time limit exceeded
21 Halted 0 ms 0 KB -