oj.uz

답안 #571299

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
571299 2022-06-01T16:47:57 Z Vanilla 자매 도시 (APIO20_swap) C++17
13 / 100
 412 ms 87300 KB 
#include "swap.h"
#include <bits/stdc++.h>
using namespace std;
const int maxn = 4e5 + 5;
int extra = 2e5 + 1;
// int extra = 9;
const int lg = 30;
vector <int> ad [maxn];
int deg [maxn];
int dad [maxn];
vector <int> val (maxn, 1e9);
vector <bool> good (maxn, 0);
vector <int> cmp [maxn];
vector <int> depth (maxn);
int up[maxn][lg];
 
void dfs (int u, int vs) {
    if (good[u]) vs = val[u];
    val[u] = vs;
    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, vs);
    }
}
 
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] = (dad[x] == x ? x: get_dad(dad[x]));
}
 
bool propagate (int u) {
  for (int v: ad[u]) {
    good[u]= good[u] | propagate(v);
  }
  return good[u];
}
 
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) {
    int p1 = get_dad(u);
    int p2 = get_dad(v);
    deg[u]++;
    deg[v]++;
    val[++extra] = cost;
    dad[p1] = extra;
    dad[p2] = extra;
    cmp[extra].push_back(p1);
    if (p1 != p2) cmp[extra].push_back(p2);
    if (p1 == p2 || deg[u] >= 3 || deg[v] >= 3) {
      good[extra] = 1;
    }
  
  }
  propagate(extra);
  dfs(extra, 1e9);

}
 
int getMinimumFuelCapacity(int x, int y) {
  int k = lca(x,y);
  if (val[k] == 1e9) return -1;
  return val[k];
}

Subtask #1
6.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 38 ms 70732 KB Output is correct
2 Correct 40 ms 70768 KB Output is correct
3 Correct 40 ms 70784 KB Output is correct
4 Correct 39 ms 70836 KB Output is correct
5 Correct 39 ms 70860 KB Output is correct
6 Correct 46 ms 70868 KB Output is correct
7 Correct 46 ms 70828 KB Output is correct
8 Correct 40 ms 70864 KB Output is correct
9 Correct 152 ms 76324 KB Output is correct
10 Correct 154 ms 77572 KB Output is correct
11 Correct 152 ms 77408 KB Output is correct
12 Correct 170 ms 77844 KB Output is correct
13 Correct 168 ms 81720 KB Output is correct
14 Correct 147 ms 76448 KB Output is correct
15 Correct 298 ms 79096 KB Output is correct
16 Correct 301 ms 78868 KB Output is correct
17 Correct 291 ms 79396 KB Output is correct
18 Correct 397 ms 83320 KB Output is correct
19 Correct 134 ms 75092 KB Output is correct
20 Correct 280 ms 79348 KB Output is correct
21 Correct 289 ms 79412 KB Output is correct
22 Correct 294 ms 79832 KB Output is correct
23 Correct 412 ms 83684 KB Output is correct

Subtask #2
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 38 ms 70732 KB Output is correct
2 Correct 40 ms 70768 KB Output is correct
3 Correct 330 ms 86680 KB Output is correct
4 Correct 332 ms 87300 KB Output is correct
5 Correct 328 ms 87108 KB Output is correct
6 Correct 320 ms 87184 KB Output is correct
7 Correct 337 ms 87288 KB Output is correct
8 Correct 334 ms 86800 KB Output is correct
9 Correct 324 ms 87108 KB Output is correct
10 Correct 313 ms 86584 KB Output is correct

Subtask #3
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 38 ms 70732 KB Output is correct
2 Correct 40 ms 70768 KB Output is correct
3 Correct 40 ms 70784 KB Output is correct
4 Correct 39 ms 70836 KB Output is correct
5 Correct 39 ms 70860 KB Output is correct
6 Correct 46 ms 70868 KB Output is correct
7 Correct 46 ms 70828 KB Output is correct
8 Correct 40 ms 70864 KB Output is correct
9 Correct 40 ms 70676 KB Output is correct
10 Correct 38 ms 70792 KB Output is correct
11 Incorrect 42 ms 70796 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 40 ms 70676 KB Output is correct
2 Correct 38 ms 70732 KB Output is correct
3 Correct 40 ms 70768 KB Output is correct
4 Correct 40 ms 70784 KB Output is correct
5 Correct 39 ms 70836 KB Output is correct
6 Correct 39 ms 70860 KB Output is correct
7 Correct 46 ms 70868 KB Output is correct
8 Correct 46 ms 70828 KB Output is correct
9 Correct 40 ms 70864 KB Output is correct
10 Correct 152 ms 76324 KB Output is correct
11 Correct 154 ms 77572 KB Output is correct
12 Correct 152 ms 77408 KB Output is correct
13 Correct 170 ms 77844 KB Output is correct
14 Correct 168 ms 81720 KB Output is correct
15 Correct 38 ms 70792 KB Output is correct
16 Incorrect 42 ms 70796 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 38 ms 70732 KB Output is correct
2 Correct 40 ms 70768 KB Output is correct
3 Correct 40 ms 70784 KB Output is correct
4 Correct 39 ms 70836 KB Output is correct
5 Correct 39 ms 70860 KB Output is correct
6 Correct 46 ms 70868 KB Output is correct
7 Correct 46 ms 70828 KB Output is correct
8 Correct 40 ms 70864 KB Output is correct
9 Correct 152 ms 76324 KB Output is correct
10 Correct 154 ms 77572 KB Output is correct
11 Correct 152 ms 77408 KB Output is correct
12 Correct 170 ms 77844 KB Output is correct
13 Correct 168 ms 81720 KB Output is correct
14 Correct 147 ms 76448 KB Output is correct
15 Correct 298 ms 79096 KB Output is correct
16 Correct 301 ms 78868 KB Output is correct
17 Correct 291 ms 79396 KB Output is correct
18 Correct 397 ms 83320 KB Output is correct
19 Correct 330 ms 86680 KB Output is correct
20 Correct 332 ms 87300 KB Output is correct
21 Correct 328 ms 87108 KB Output is correct
22 Correct 320 ms 87184 KB Output is correct
23 Correct 337 ms 87288 KB Output is correct
24 Correct 334 ms 86800 KB Output is correct
25 Correct 324 ms 87108 KB Output is correct
26 Correct 313 ms 86584 KB Output is correct
27 Correct 38 ms 70792 KB Output is correct
28 Incorrect 42 ms 70796 KB Output isn't correct
29 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 40 ms 70676 KB Output is correct
2 Correct 38 ms 70732 KB Output is correct
3 Correct 40 ms 70768 KB Output is correct
4 Correct 40 ms 70784 KB Output is correct
5 Correct 39 ms 70836 KB Output is correct
6 Correct 39 ms 70860 KB Output is correct
7 Correct 46 ms 70868 KB Output is correct
8 Correct 46 ms 70828 KB Output is correct
9 Correct 40 ms 70864 KB Output is correct
10 Correct 152 ms 76324 KB Output is correct
11 Correct 154 ms 77572 KB Output is correct
12 Correct 152 ms 77408 KB Output is correct
13 Correct 170 ms 77844 KB Output is correct
14 Correct 168 ms 81720 KB Output is correct
15 Correct 147 ms 76448 KB Output is correct
16 Correct 298 ms 79096 KB Output is correct
17 Correct 301 ms 78868 KB Output is correct
18 Correct 291 ms 79396 KB Output is correct
19 Correct 397 ms 83320 KB Output is correct
20 Correct 330 ms 86680 KB Output is correct
21 Correct 332 ms 87300 KB Output is correct
22 Correct 328 ms 87108 KB Output is correct
23 Correct 320 ms 87184 KB Output is correct
24 Correct 337 ms 87288 KB Output is correct
25 Correct 334 ms 86800 KB Output is correct
26 Correct 324 ms 87108 KB Output is correct
27 Correct 313 ms 86584 KB Output is correct
28 Correct 38 ms 70792 KB Output is correct
29 Incorrect 42 ms 70796 KB Output isn't correct
30 Halted 0 ms 0 KB -