oj.uz

답안 #899510

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
899510 2024-01-06T10:58:02 Z rxlfd314 Split the Attractions (IOI19_split) C++17
29 / 100
 59 ms 13632 KB 
#include "split.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ari2 = array<int, 2>;
using ari3 = array<int, 3>;

#define vt vector
#define size(x) (int((x).size()))
#define all(x) begin(x), end(x)

#define REP(a, b, c, d) for (int a = (b); (d) > 0 ? a <= (c) : a >= (c); a += (d))
#define FOR(a, b, c) REP(a, b, c, 1)
#define ROF(a, b, c) REP(a, b, c, -1)

vt<int> find_split(int N, int X, int Y, int Z, vt<int> P, vt<int> Q) {
  ari2 A = {X, 1}, B = {Y, 2}, C = {Z, 3};
  if (B > C)
    swap(B, C);
  if (A > B)
    swap(A, B);
  if (B > C)
    swap(B, C);
  vt<int> adj[N];
  bool sub1 = true;
  FOR(i, 0, size(P)-1) {
    adj[P[i]].push_back(Q[i]);
    adj[Q[i]].push_back(P[i]);
    sub1 &= size(adj[P[i]]) < 3 && size(adj[Q[i]]) < 3;
  }
  if (sub1) {
    int s = 0;
    FOR(i, 0, N-1)
      if (size(adj[i]) == 1)
        s = i;
    int cur = s, p = s;
    vt<int> ans(N, C[1]);
    while (A[0]--) {
      ans[cur] = A[1];
      for (int i : adj[cur])
        if (i != p) {
          p = cur;
          cur = i;
          break;
        }
    }
    while (B[0]--) {
      ans[cur] = B[1];
      for (int i : adj[cur])
        if (i != p) {
          p = cur;
          cur = i;
          break;
        }
    }
    return ans;
  }
  if (size(P) == N-1) {
    #ifdef DEBUG
    cout << "LOL\n";
    #endif
    int szs[N];
    function<int(int, int)> calc_sizes = [&](int i, int p) {
      #ifdef DEBUG
      cout << "cs: " << i << '\n';
      #endif
      szs[i] = 1;
      for (int j : adj[i])
        if (j != p)
          szs[i] += calc_sizes(j, i);
      return szs[i];
    };
    calc_sizes(0, 0);
    function<void(int, int, ari2&, vt<int>&)> dfs = [&](int i, int p, ari2 &v, vt<int> &ans) {
      #ifdef DEBUG
      cout << "dfs: " << i << '\n';
      #endif
      if (!v[0])
        return;
      ans[i] = v[1];
      v[0]--;
      for (int j : adj[i])
        if (j != p)
          dfs(j, i, v, ans);
    };
    vt<int> ans(N, C[1]);
    bool found = false;
    function<void(int, int)> reroot = [&](int i, int p) {
      if (found)
        return;
      #ifdef DEBUG
      cout << "reroot " << i << '\n';
      #endif
      for (int j : adj[i])
        if (szs[i] - szs[j] >= A[0] && szs[j] >= B[0]) {
          dfs(i, j, A, ans);
          dfs(j, i, B, ans);
          found = true;
          return;
        }
      for (int j : adj[i])
        if (j != p) {
          int x = szs[j];
          szs[j] = N;
          szs[i] -= x;
          reroot(j, i);
          szs[i] += x;
          szs[j] = x;
        }
    };
    reroot(0, 0);
    if (found)
      return ans;
    return vt<int>(N, 0);
  }
  if (A[0] == 1) {
    bool seen[N] = {};
    int cnt = A[0] + B[0];
    function<void(int)> dfs = [&](int i) {
      if (seen[i] || !cnt)
        return;
      seen[i] = true;
      cnt--;
      for (int j : adj[i])
        dfs(j);
    };
    dfs(0);
    vt<int> adj2[N];
    FOR(i, 0, N-1)
      if (seen[i]) {
        #ifdef DEBUG
        cout << i << ' ';
        #endif
        for (int j : adj[i])
          if (seen[j])
            adj2[i].push_back(j);
      }
    #ifdef DEBUG
    cout << '\n';
    #endif
    int tin[N], low[N], timer = 0;
    memset(tin, -1, sizeof(tin));
    set<ari2> bridges;
    function<void(int, int)> dfs2 = [&](int i, int p) {
      low[i] = tin[i] = timer++;
      for (int j : adj2[i]) {
        if (j == p || !seen[j])
          continue;
        if (~tin[j])
          low[i] = min(low[i], tin[j]);
        else {
          dfs2(j, i);
          low[i] = min(low[i], low[j]);
          if (tin[i] > low[j] && size(adj2[i]) > 1) {
            bridges.insert({i, j});
            bridges.insert({j, i});
          }
        }
      }
    };
    FOR(r, 0, N-1)
      if (seen[r]) {
        dfs2(r, r);
        vt<int> ans(N, C[1]);
        int special;
        FOR(i, 0, N-1)
          if (seen[i]) {
            for (int j : adj2[i])
              if (!bridges.count({i, j}))
                special = i;
            ans[i] = B[1];
          }
        #ifdef DEBUG
        cout << "special node " << special << '\n';
        #endif
        ans[special] = A[1];
        return ans;
      }
  }
}

Compilation message

split.cpp: In function 'std::vector<int> find_split(int, int, int, int, std::vector<int>, std::vector<int>)':
split.cpp:180:1: warning: control reaches end of non-void function [-Wreturn-type]
  180 | }
      | ^
split.cpp:176:20: warning: 'special' may be used uninitialized in this function [-Wmaybe-uninitialized]
  176 |         ans[special] = A[1];
      |                    ^

Subtask #1
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB ok, correct split
2 Correct 0 ms 348 KB ok, correct split
3 Correct 0 ms 440 KB ok, correct split
4 Correct 0 ms 348 KB ok, correct split
5 Correct 0 ms 344 KB ok, correct split
6 Correct 0 ms 436 KB ok, correct split
7 Correct 39 ms 8884 KB ok, correct split
8 Correct 36 ms 8788 KB ok, correct split
9 Correct 38 ms 8784 KB ok, correct split
10 Correct 35 ms 8796 KB ok, correct split
11 Correct 37 ms 8788 KB ok, correct split

Subtask #2
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 344 KB ok, correct split
2 Correct 0 ms 348 KB ok, correct split
3 Incorrect 0 ms 436 KB 2 components are not connected
4 Halted 0 ms 0 KB -

Subtask #3
22.0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB ok, correct split
2 Correct 41 ms 9376 KB ok, correct split
3 Correct 17 ms 3932 KB ok, correct split
4 Correct 0 ms 344 KB ok, correct split
5 Correct 46 ms 12364 KB ok, correct split
6 Correct 56 ms 12312 KB ok, correct split
7 Correct 46 ms 13236 KB ok, correct split
8 Correct 49 ms 13632 KB ok, correct split
9 Correct 59 ms 13140 KB ok, correct split
10 Correct 14 ms 3416 KB ok, no valid answer
11 Correct 22 ms 4956 KB ok, no valid answer
12 Correct 39 ms 9944 KB ok, no valid answer
13 Correct 43 ms 9808 KB ok, no valid answer
14 Correct 35 ms 10184 KB ok, no valid answer

Subtask #4
0 / 24.0

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

Subtask #5
0 / 36.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB ok, correct split
2 Correct 0 ms 348 KB ok, correct split
3 Correct 0 ms 440 KB ok, correct split
4 Correct 0 ms 348 KB ok, correct split
5 Correct 0 ms 344 KB ok, correct split
6 Correct 0 ms 436 KB ok, correct split
7 Correct 39 ms 8884 KB ok, correct split
8 Correct 36 ms 8788 KB ok, correct split
9 Correct 38 ms 8784 KB ok, correct split
10 Correct 35 ms 8796 KB ok, correct split
11 Correct 37 ms 8788 KB ok, correct split
12 Correct 0 ms 344 KB ok, correct split
13 Correct 0 ms 348 KB ok, correct split
14 Incorrect 0 ms 436 KB 2 components are not connected
15 Halted 0 ms 0 KB -