oj.uz

답안 #571292

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
571292 2022-06-01T16:31:55 Z Vanilla 자매 도시 (APIO20_swap) C++17
13 / 100
 530 ms 82868 KB 
#include "swap.h"
#include <bits/stdc++.h>
using namespace std;
const int maxn = 4e5 + 2;
int extra = 2e5 + 1;
// int extra = 9;
const int lg = 25;
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];
    else 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;
  good [maxn - 1] = 1;
  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;
    }
  
  }
  for (int i = maxn - 1; i >= 0; i--){
    if (!cmp[i].empty()) {
      propagate(i);
      dfs(i, 1e9);
      break;
    }
  }
 
}
 
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 41 ms 62924 KB Output is correct
2 Correct 31 ms 62976 KB Output is correct
3 Correct 33 ms 62932 KB Output is correct
4 Correct 32 ms 62932 KB Output is correct
5 Correct 30 ms 62928 KB Output is correct
6 Correct 36 ms 63000 KB Output is correct
7 Correct 43 ms 62980 KB Output is correct
8 Correct 36 ms 63036 KB Output is correct
9 Correct 138 ms 70152 KB Output is correct
10 Correct 185 ms 71728 KB Output is correct
11 Correct 168 ms 71520 KB Output is correct
12 Correct 180 ms 72076 KB Output is correct
13 Correct 172 ms 75980 KB Output is correct
14 Correct 167 ms 70408 KB Output is correct
15 Correct 298 ms 75164 KB Output is correct
16 Correct 310 ms 74868 KB Output is correct
17 Correct 331 ms 75440 KB Output is correct
18 Correct 530 ms 79360 KB Output is correct
19 Correct 172 ms 69336 KB Output is correct
20 Correct 385 ms 75216 KB Output is correct
21 Correct 352 ms 75376 KB Output is correct
22 Correct 333 ms 75856 KB Output is correct
23 Correct 465 ms 79808 KB Output is correct

Subtask #2
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 41 ms 62924 KB Output is correct
2 Correct 31 ms 62976 KB Output is correct
3 Correct 373 ms 82184 KB Output is correct
4 Correct 394 ms 82712 KB Output is correct
5 Correct 362 ms 82748 KB Output is correct
6 Correct 402 ms 82664 KB Output is correct
7 Correct 384 ms 82868 KB Output is correct
8 Correct 458 ms 82212 KB Output is correct
9 Correct 388 ms 82556 KB Output is correct
10 Correct 396 ms 82108 KB Output is correct

Subtask #3
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 41 ms 62924 KB Output is correct
2 Correct 31 ms 62976 KB Output is correct
3 Correct 33 ms 62932 KB Output is correct
4 Correct 32 ms 62932 KB Output is correct
5 Correct 30 ms 62928 KB Output is correct
6 Correct 36 ms 63000 KB Output is correct
7 Correct 43 ms 62980 KB Output is correct
8 Correct 36 ms 63036 KB Output is correct
9 Correct 35 ms 62880 KB Output is correct
10 Correct 39 ms 63020 KB Output is correct
11 Incorrect 41 ms 62992 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 35 ms 62880 KB Output is correct
2 Correct 41 ms 62924 KB Output is correct
3 Correct 31 ms 62976 KB Output is correct
4 Correct 33 ms 62932 KB Output is correct
5 Correct 32 ms 62932 KB Output is correct
6 Correct 30 ms 62928 KB Output is correct
7 Correct 36 ms 63000 KB Output is correct
8 Correct 43 ms 62980 KB Output is correct
9 Correct 36 ms 63036 KB Output is correct
10 Correct 138 ms 70152 KB Output is correct
11 Correct 185 ms 71728 KB Output is correct
12 Correct 168 ms 71520 KB Output is correct
13 Correct 180 ms 72076 KB Output is correct
14 Correct 172 ms 75980 KB Output is correct
15 Correct 39 ms 63020 KB Output is correct
16 Incorrect 41 ms 62992 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 41 ms 62924 KB Output is correct
2 Correct 31 ms 62976 KB Output is correct
3 Correct 33 ms 62932 KB Output is correct
4 Correct 32 ms 62932 KB Output is correct
5 Correct 30 ms 62928 KB Output is correct
6 Correct 36 ms 63000 KB Output is correct
7 Correct 43 ms 62980 KB Output is correct
8 Correct 36 ms 63036 KB Output is correct
9 Correct 138 ms 70152 KB Output is correct
10 Correct 185 ms 71728 KB Output is correct
11 Correct 168 ms 71520 KB Output is correct
12 Correct 180 ms 72076 KB Output is correct
13 Correct 172 ms 75980 KB Output is correct
14 Correct 167 ms 70408 KB Output is correct
15 Correct 298 ms 75164 KB Output is correct
16 Correct 310 ms 74868 KB Output is correct
17 Correct 331 ms 75440 KB Output is correct
18 Correct 530 ms 79360 KB Output is correct
19 Correct 373 ms 82184 KB Output is correct
20 Correct 394 ms 82712 KB Output is correct
21 Correct 362 ms 82748 KB Output is correct
22 Correct 402 ms 82664 KB Output is correct
23 Correct 384 ms 82868 KB Output is correct
24 Correct 458 ms 82212 KB Output is correct
25 Correct 388 ms 82556 KB Output is correct
26 Correct 396 ms 82108 KB Output is correct
27 Correct 39 ms 63020 KB Output is correct
28 Incorrect 41 ms 62992 KB Output isn't correct
29 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 35 ms 62880 KB Output is correct
2 Correct 41 ms 62924 KB Output is correct
3 Correct 31 ms 62976 KB Output is correct
4 Correct 33 ms 62932 KB Output is correct
5 Correct 32 ms 62932 KB Output is correct
6 Correct 30 ms 62928 KB Output is correct
7 Correct 36 ms 63000 KB Output is correct
8 Correct 43 ms 62980 KB Output is correct
9 Correct 36 ms 63036 KB Output is correct
10 Correct 138 ms 70152 KB Output is correct
11 Correct 185 ms 71728 KB Output is correct
12 Correct 168 ms 71520 KB Output is correct
13 Correct 180 ms 72076 KB Output is correct
14 Correct 172 ms 75980 KB Output is correct
15 Correct 167 ms 70408 KB Output is correct
16 Correct 298 ms 75164 KB Output is correct
17 Correct 310 ms 74868 KB Output is correct
18 Correct 331 ms 75440 KB Output is correct
19 Correct 530 ms 79360 KB Output is correct
20 Correct 373 ms 82184 KB Output is correct
21 Correct 394 ms 82712 KB Output is correct
22 Correct 362 ms 82748 KB Output is correct
23 Correct 402 ms 82664 KB Output is correct
24 Correct 384 ms 82868 KB Output is correct
25 Correct 458 ms 82212 KB Output is correct
26 Correct 388 ms 82556 KB Output is correct
27 Correct 396 ms 82108 KB Output is correct
28 Correct 39 ms 63020 KB Output is correct
29 Incorrect 41 ms 62992 KB Output isn't correct
30 Halted 0 ms 0 KB -