oj.uz

답안 #571304

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
571304 2022-06-01T16:54:55 Z Vanilla 자매 도시 (APIO20_swap) C++17
13 / 100
 464 ms 57212 KB 
#include "swap.h"
#include <bits/stdc++.h>
using namespace std;
const int maxn = 3e5 + 200;
int extra = 1e5 + 1;
const int lg = 29;
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 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);
    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 + 1,y + 1);
  if (val[k] == 1e9) return -1;
  return val[k];
}

Subtask #1
6.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 11 ms 17876 KB Output is correct
2 Correct 9 ms 17876 KB Output is correct
3 Correct 10 ms 17960 KB Output is correct
4 Correct 9 ms 18004 KB Output is correct
5 Correct 10 ms 18192 KB Output is correct
6 Correct 11 ms 18132 KB Output is correct
7 Correct 11 ms 18260 KB Output is correct
8 Correct 11 ms 18260 KB Output is correct
9 Correct 117 ms 41320 KB Output is correct
10 Correct 139 ms 46464 KB Output is correct
11 Correct 132 ms 46116 KB Output is correct
12 Correct 140 ms 47664 KB Output is correct
13 Correct 144 ms 51520 KB Output is correct
14 Correct 121 ms 41404 KB Output is correct
15 Correct 274 ms 48276 KB Output is correct
16 Correct 253 ms 47556 KB Output is correct
17 Correct 258 ms 49288 KB Output is correct
18 Correct 419 ms 53152 KB Output is correct
19 Correct 105 ms 25928 KB Output is correct
20 Correct 315 ms 48684 KB Output is correct
21 Correct 335 ms 47768 KB Output is correct
22 Correct 347 ms 49636 KB Output is correct
23 Correct 464 ms 53552 KB Output is correct

Subtask #2
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 11 ms 17876 KB Output is correct
2 Correct 9 ms 17876 KB Output is correct
3 Correct 352 ms 55340 KB Output is correct
4 Correct 349 ms 57212 KB Output is correct
5 Correct 360 ms 56092 KB Output is correct
6 Correct 311 ms 56936 KB Output is correct
7 Correct 309 ms 56612 KB Output is correct
8 Correct 339 ms 55080 KB Output is correct
9 Correct 309 ms 56280 KB Output is correct
10 Correct 350 ms 54820 KB Output is correct

Subtask #3
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 11 ms 17876 KB Output is correct
2 Correct 9 ms 17876 KB Output is correct
3 Correct 10 ms 17960 KB Output is correct
4 Correct 9 ms 18004 KB Output is correct
5 Correct 10 ms 18192 KB Output is correct
6 Correct 11 ms 18132 KB Output is correct
7 Correct 11 ms 18260 KB Output is correct
8 Correct 11 ms 18260 KB Output is correct
9 Correct 10 ms 17876 KB Output is correct
10 Correct 11 ms 18260 KB Output is correct
11 Incorrect 11 ms 18260 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 10 ms 17876 KB Output is correct
2 Correct 11 ms 17876 KB Output is correct
3 Correct 9 ms 17876 KB Output is correct
4 Correct 10 ms 17960 KB Output is correct
5 Correct 9 ms 18004 KB Output is correct
6 Correct 10 ms 18192 KB Output is correct
7 Correct 11 ms 18132 KB Output is correct
8 Correct 11 ms 18260 KB Output is correct
9 Correct 11 ms 18260 KB Output is correct
10 Correct 117 ms 41320 KB Output is correct
11 Correct 139 ms 46464 KB Output is correct
12 Correct 132 ms 46116 KB Output is correct
13 Correct 140 ms 47664 KB Output is correct
14 Correct 144 ms 51520 KB Output is correct
15 Correct 11 ms 18260 KB Output is correct
16 Incorrect 11 ms 18260 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 11 ms 17876 KB Output is correct
2 Correct 9 ms 17876 KB Output is correct
3 Correct 10 ms 17960 KB Output is correct
4 Correct 9 ms 18004 KB Output is correct
5 Correct 10 ms 18192 KB Output is correct
6 Correct 11 ms 18132 KB Output is correct
7 Correct 11 ms 18260 KB Output is correct
8 Correct 11 ms 18260 KB Output is correct
9 Correct 117 ms 41320 KB Output is correct
10 Correct 139 ms 46464 KB Output is correct
11 Correct 132 ms 46116 KB Output is correct
12 Correct 140 ms 47664 KB Output is correct
13 Correct 144 ms 51520 KB Output is correct
14 Correct 121 ms 41404 KB Output is correct
15 Correct 274 ms 48276 KB Output is correct
16 Correct 253 ms 47556 KB Output is correct
17 Correct 258 ms 49288 KB Output is correct
18 Correct 419 ms 53152 KB Output is correct
19 Correct 352 ms 55340 KB Output is correct
20 Correct 349 ms 57212 KB Output is correct
21 Correct 360 ms 56092 KB Output is correct
22 Correct 311 ms 56936 KB Output is correct
23 Correct 309 ms 56612 KB Output is correct
24 Correct 339 ms 55080 KB Output is correct
25 Correct 309 ms 56280 KB Output is correct
26 Correct 350 ms 54820 KB Output is correct
27 Correct 11 ms 18260 KB Output is correct
28 Incorrect 11 ms 18260 KB Output isn't correct
29 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 10 ms 17876 KB Output is correct
2 Correct 11 ms 17876 KB Output is correct
3 Correct 9 ms 17876 KB Output is correct
4 Correct 10 ms 17960 KB Output is correct
5 Correct 9 ms 18004 KB Output is correct
6 Correct 10 ms 18192 KB Output is correct
7 Correct 11 ms 18132 KB Output is correct
8 Correct 11 ms 18260 KB Output is correct
9 Correct 11 ms 18260 KB Output is correct
10 Correct 117 ms 41320 KB Output is correct
11 Correct 139 ms 46464 KB Output is correct
12 Correct 132 ms 46116 KB Output is correct
13 Correct 140 ms 47664 KB Output is correct
14 Correct 144 ms 51520 KB Output is correct
15 Correct 121 ms 41404 KB Output is correct
16 Correct 274 ms 48276 KB Output is correct
17 Correct 253 ms 47556 KB Output is correct
18 Correct 258 ms 49288 KB Output is correct
19 Correct 419 ms 53152 KB Output is correct
20 Correct 352 ms 55340 KB Output is correct
21 Correct 349 ms 57212 KB Output is correct
22 Correct 360 ms 56092 KB Output is correct
23 Correct 311 ms 56936 KB Output is correct
24 Correct 309 ms 56612 KB Output is correct
25 Correct 339 ms 55080 KB Output is correct
26 Correct 309 ms 56280 KB Output is correct
27 Correct 350 ms 54820 KB Output is correct
28 Correct 11 ms 18260 KB Output is correct
29 Incorrect 11 ms 18260 KB Output isn't correct
30 Halted 0 ms 0 KB -