oj.uz

답안 #571279

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
571279 2022-06-01T16:00:34 Z Vanilla 자매 도시 (APIO20_swap) C++17
6 / 100
 2000 ms 77180 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];
int val [maxn];
bitset <maxn> good;
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] || !good[up[x][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 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;
  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++){
    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);
    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 = 0; i <= 16; i++) {
  //   cout << good[i] << " " << val[i] << " ";
  //   cout << i << ": ";
  //   for (int j: cmp[i]) {
  //     cout << j << " ";
  //   }
  //   cout << '\n';
  // }
  for (int i = maxn - 1; i >= 0; i--){
    if (!cmp[i].empty()) {
      dfs(i);
      break;
    }
  }
 
}
 
int getMinimumFuelCapacity(int x, int y) {
  int k = lca(x,y);
  if (!good[k] || k == maxn - 1) return -1;
  return val[k];
}

Subtask #1
6.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 29 ms 61276 KB Output is correct
2 Correct 28 ms 61340 KB Output is correct
3 Correct 31 ms 61384 KB Output is correct
4 Correct 33 ms 61416 KB Output is correct
5 Correct 29 ms 61432 KB Output is correct
6 Correct 30 ms 61376 KB Output is correct
7 Correct 32 ms 61452 KB Output is correct
8 Correct 30 ms 61512 KB Output is correct
9 Correct 149 ms 69188 KB Output is correct
10 Correct 144 ms 70928 KB Output is correct
11 Correct 140 ms 70704 KB Output is correct
12 Correct 163 ms 71244 KB Output is correct
13 Correct 160 ms 74460 KB Output is correct
14 Correct 128 ms 69440 KB Output is correct
15 Correct 299 ms 73288 KB Output is correct
16 Correct 276 ms 73012 KB Output is correct
17 Correct 311 ms 73636 KB Output is correct
18 Correct 416 ms 76716 KB Output is correct
19 Correct 180 ms 67824 KB Output is correct
20 Correct 292 ms 73520 KB Output is correct
21 Correct 326 ms 73644 KB Output is correct
22 Correct 317 ms 73984 KB Output is correct
23 Correct 419 ms 77180 KB Output is correct

Subtask #2
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 29 ms 61276 KB Output is correct
2 Correct 28 ms 61340 KB Output is correct
3 Execution timed out 2058 ms 71400 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 29 ms 61276 KB Output is correct
2 Correct 28 ms 61340 KB Output is correct
3 Correct 31 ms 61384 KB Output is correct
4 Correct 33 ms 61416 KB Output is correct
5 Correct 29 ms 61432 KB Output is correct
6 Correct 30 ms 61376 KB Output is correct
7 Correct 32 ms 61452 KB Output is correct
8 Correct 30 ms 61512 KB Output is correct
9 Correct 37 ms 61388 KB Output is correct
10 Incorrect 35 ms 61400 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 37 ms 61388 KB Output is correct
2 Correct 29 ms 61276 KB Output is correct
3 Correct 28 ms 61340 KB Output is correct
4 Correct 31 ms 61384 KB Output is correct
5 Correct 33 ms 61416 KB Output is correct
6 Correct 29 ms 61432 KB Output is correct
7 Correct 30 ms 61376 KB Output is correct
8 Correct 32 ms 61452 KB Output is correct
9 Correct 30 ms 61512 KB Output is correct
10 Correct 149 ms 69188 KB Output is correct
11 Correct 144 ms 70928 KB Output is correct
12 Correct 140 ms 70704 KB Output is correct
13 Correct 163 ms 71244 KB Output is correct
14 Correct 160 ms 74460 KB Output is correct
15 Incorrect 35 ms 61400 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 29 ms 61276 KB Output is correct
2 Correct 28 ms 61340 KB Output is correct
3 Correct 31 ms 61384 KB Output is correct
4 Correct 33 ms 61416 KB Output is correct
5 Correct 29 ms 61432 KB Output is correct
6 Correct 30 ms 61376 KB Output is correct
7 Correct 32 ms 61452 KB Output is correct
8 Correct 30 ms 61512 KB Output is correct
9 Correct 149 ms 69188 KB Output is correct
10 Correct 144 ms 70928 KB Output is correct
11 Correct 140 ms 70704 KB Output is correct
12 Correct 163 ms 71244 KB Output is correct
13 Correct 160 ms 74460 KB Output is correct
14 Correct 128 ms 69440 KB Output is correct
15 Correct 299 ms 73288 KB Output is correct
16 Correct 276 ms 73012 KB Output is correct
17 Correct 311 ms 73636 KB Output is correct
18 Correct 416 ms 76716 KB Output is correct
19 Execution timed out 2058 ms 71400 KB Time limit exceeded
20 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 37 ms 61388 KB Output is correct
2 Correct 29 ms 61276 KB Output is correct
3 Correct 28 ms 61340 KB Output is correct
4 Correct 31 ms 61384 KB Output is correct
5 Correct 33 ms 61416 KB Output is correct
6 Correct 29 ms 61432 KB Output is correct
7 Correct 30 ms 61376 KB Output is correct
8 Correct 32 ms 61452 KB Output is correct
9 Correct 30 ms 61512 KB Output is correct
10 Correct 149 ms 69188 KB Output is correct
11 Correct 144 ms 70928 KB Output is correct
12 Correct 140 ms 70704 KB Output is correct
13 Correct 163 ms 71244 KB Output is correct
14 Correct 160 ms 74460 KB Output is correct
15 Correct 128 ms 69440 KB Output is correct
16 Correct 299 ms 73288 KB Output is correct
17 Correct 276 ms 73012 KB Output is correct
18 Correct 311 ms 73636 KB Output is correct
19 Correct 416 ms 76716 KB Output is correct
20 Execution timed out 2058 ms 71400 KB Time limit exceeded
21 Halted 0 ms 0 KB -