oj.uz

답안 #420551

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
420551 2021-06-08T12:37:47 Z SSRS Split the Attractions (IOI19_split) C++14
18 / 100
 128 ms 17040 KB 
#include <bits/stdc++.h>
using namespace std;
void dfs(vector<vector<int>> &E, vector<bool> &used, vector<int> &d, int v){
  d.push_back(v);
  for (int w : E[v]){
    if (!used[w]){
      used[w] = true;
      dfs(E, used, d, w);
    }
  }
}
vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q){
  int m = p.size();
  vector<vector<int>> E(n);
  for (int i = 0; i < m; i++){
    E[p[i]].push_back(q[i]);
    E[q[i]].push_back(p[i]);
  }
  if (a != 1){
    for (int i = 0; i < n; i++){
      assert(E[i].size() <= 2);
    }
    int s = 0;
    for (int i = 0; i < n; i++){
      if (E[i].size() == 1){
        s = i;
      }
    }
    vector<bool> used(n, false);
    used[s] = true;
    vector<int> d;
    dfs(E, used, d, s);
    vector<int> ans(n);
    for (int i = 0; i < a; i++){
      ans[d[i]] = 1;
    }
    for (int i = a; i < a + b; i++){
      ans[d[i]] = 2;
    }
    for (int i = a + b; i < a + b + c; i++){
      ans[d[i]] = 3;
    }
    return ans;
  } else {
    vector<bool> used(n, false);
    used[0] = true;
    vector<int> d;
    dfs(E, used, d, 0);
    vector<int> ans(n);
    for (int i = 0; i < b; i++){
      ans[d[i]] = 2;
    }
    ans[d[b]] = 1;
    for (int i = b + 1; i < n; i++){
      ans[d[i]] = 3;
    }
    return ans;
  }
}

Subtask #1
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 204 KB ok, correct split
2 Correct 0 ms 204 KB ok, correct split
3 Correct 0 ms 204 KB ok, correct split
4 Correct 1 ms 204 KB ok, correct split
5 Correct 1 ms 204 KB ok, correct split
6 Correct 0 ms 204 KB ok, correct split
7 Correct 81 ms 16044 KB ok, correct split
8 Correct 78 ms 13380 KB ok, correct split
9 Correct 84 ms 16044 KB ok, correct split
10 Correct 72 ms 16068 KB ok, correct split
11 Correct 80 ms 15996 KB ok, correct split

Subtask #2
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 204 KB ok, correct split
2 Correct 1 ms 204 KB ok, correct split
3 Correct 1 ms 204 KB ok, correct split
4 Correct 119 ms 13944 KB ok, correct split
5 Correct 80 ms 9244 KB ok, correct split
6 Correct 87 ms 17040 KB ok, correct split
7 Correct 78 ms 14224 KB ok, correct split
8 Correct 128 ms 11552 KB ok, correct split
9 Correct 77 ms 9264 KB ok, correct split
10 Correct 57 ms 9408 KB ok, correct split
11 Correct 54 ms 9380 KB ok, correct split
12 Correct 60 ms 9592 KB ok, correct split

Subtask #3
0 / 22.0

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

Subtask #4
0 / 24.0

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

Subtask #5
0 / 36.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 204 KB ok, correct split
2 Correct 0 ms 204 KB ok, correct split
3 Correct 0 ms 204 KB ok, correct split
4 Correct 1 ms 204 KB ok, correct split
5 Correct 1 ms 204 KB ok, correct split
6 Correct 0 ms 204 KB ok, correct split
7 Correct 81 ms 16044 KB ok, correct split
8 Correct 78 ms 13380 KB ok, correct split
9 Correct 84 ms 16044 KB ok, correct split
10 Correct 72 ms 16068 KB ok, correct split
11 Correct 80 ms 15996 KB ok, correct split
12 Correct 1 ms 204 KB ok, correct split
13 Correct 1 ms 204 KB ok, correct split
14 Correct 1 ms 204 KB ok, correct split
15 Correct 119 ms 13944 KB ok, correct split
16 Correct 80 ms 9244 KB ok, correct split
17 Correct 87 ms 17040 KB ok, correct split
18 Correct 78 ms 14224 KB ok, correct split
19 Correct 128 ms 11552 KB ok, correct split
20 Correct 77 ms 9264 KB ok, correct split
21 Correct 57 ms 9408 KB ok, correct split
22 Correct 54 ms 9380 KB ok, correct split
23 Correct 60 ms 9592 KB ok, correct split
24 Runtime error 1 ms 332 KB Execution killed with signal 6
25 Halted 0 ms 0 KB -