oj.uz

답안 #293417

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
293417 2020-09-08T04:44:50 Z rama_pang 자매 도시 (APIO20_swap) C++14
0 / 100
 1 ms 384 KB 
#include "swap.h"
#include <bits/stdc++.h>
using namespace std;

class DisjointSet {
 public:
  int n, t = -1;
  vector<vector<pair<int, int>>> p; // (time, data)
  vector<vector<pair<int, int>>> sz;
  vector<vector<pair<int, int>>> deg;
  vector<vector<pair<int, int>>> cycle;

  DisjointSet() {}
  DisjointSet(int n) : n(n), p(n), sz(n), deg(n), cycle(n) {
    for (int i = 0; i < n; i++) {
      p[i].emplace_back(-1, i);
      sz[i].emplace_back(-1, 1);
      deg[i].emplace_back(-1, 0);
      cycle[i].emplace_back(-1, 0);
    }
  }

  int Find(int x) {
    return p[x].back().second == x ? x : Find(p[x].back().second);
  }
  int Unite(int x, int y) {
    t++;
    x = Find(x), y = Find(y);
    if (x != y) {
      if (sz[x].back().second > sz[y].back().second) {
        swap(x, y);
      }
      p[x].emplace_back(t, y);
      sz[y].emplace_back(t, sz[y].back().second + sz[x].back().second);
      if (deg[x].back().second > deg[y].back().second) {
        deg[y].emplace_back(t, deg[x].back().second);
      }
      if (cycle[y].back().second == 0 && cycle[x].back().second == 1) {
        cycle[y].emplace_back(t, 1);
      }
      return 1;
    }
    return 0;
  }
  int UpdateCycle(int x) {
    x = Find(x);
    if (cycle[x].back().second == 0) {
      cycle[x].emplace_back(t, 1);
    }
  }
  int UpdateDegree(int x, int v) {
    x = Find(x);
    if (v > deg[x].back().second) {
      deg[x].emplace_back(t, v);
    }
  }
  int Find(int x, int tt) {
    assert(p[x].size() <= 2);
    int pp = p[x][0].second;
    if (p[x].size() > 1 && p[x][1].first <= tt) {
      pp = p[x][1].second;
    }
    return pp == x ? x : Find(pp, tt);
  }
  int Degree(int x, int tt) {
    int pos = upper_bound(begin(deg[x]), end(deg[x]), make_pair(tt, int(1e9))) - begin(deg[x]) - 1;
    return deg[x][pos].second;
  }
  int Cycle(int x, int tt) {
    int pos = upper_bound(begin(cycle[x]), end(cycle[x]), make_pair(tt, int(1e9))) - begin(cycle[x]) - 1;
    return cycle[x][pos].second;
  }
};

DisjointSet D;
vector<int> values;

bool Check(int x, int y, int m) {
  x = D.Find(x, m), y = D.Find(y, m);
  return x == y && (D.Degree(x, m) >= 3 || D.Cycle(x, m) == 1);
}

void init(int N, int M, vector<int> U, vector<int> V, vector<int> W) {
  values = W;
  sort(begin(values), end(values));
  vector<array<int, 3>> E;
  for (int i = 0; i < M; i++) {
    E.push_back({W[i], U[i], V[i]});
  }
  sort(begin(E), end(E));
  D = DisjointSet(N);
  for (int i = 0; i < M; i++) {
    static vector<int> deg(N);
    deg[E[i][1]]++, deg[E[i][2]]++;
    if (!D.Unite(E[i][1], E[i][2])) {
      D.UpdateCycle(E[i][1]);
    }
    D.UpdateDegree(E[i][1], min(3, max(deg[E[i][1]], deg[E[i][2]])));
  }
}

int getMinimumFuelCapacity(int X, int Y) {
  int lo = 0, hi = int(values.size()) - 1;
  if (!Check(X, Y, hi)) {
    return -1;
  }
  while (lo < hi) {
    int md = (lo + hi) / 2;
    if (Check(X, Y, md)) {
      hi = md;
    } else {
      lo = md + 1;
    }
  }
  return values[lo];
}

Compilation message

swap.cpp: In member function 'int DisjointSet::UpdateCycle(int)':
swap.cpp:50:3: warning: no return statement in function returning non-void [-Wreturn-type]
   50 |   }
      |   ^
swap.cpp: In member function 'int DisjointSet::UpdateDegree(int, int)':
swap.cpp:56:3: warning: no return statement in function returning non-void [-Wreturn-type]
   56 |   }
      |   ^

Subtask #1
0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 1 ms 384 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 1 ms 384 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 1 ms 384 KB Execution killed with signal 11

Subtask #4
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 1 ms 384 KB Execution killed with signal 11

Subtask #5
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 1 ms 384 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 1 ms 384 KB Execution killed with signal 11