oj.uz

Submission #979420

# Submission time Handle Problem Language Result Execution time Memory
979420 2024-05-10T23:01:19 Z AdamGS Split the Attractions (IOI19_split) C++17
40 / 100
 2000 ms 29640 KB 
#include "split.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(a, b) for(int a = 0; a < (b); ++a)
#define st first
#define nd second
#define pb push_back
#define all(a) a.begin(), a.end()
const int LIM=1e5+7;
vector<int>V[LIM], G[LIM], P[LIM], ans;
vector<pair<int,int>>S;
int odl[LIM], pre[LIM], ile[LIM], lpre;
void DFS(int x) {
  pre[x]=++lpre;
  ile[x]=1;
  for(auto i : V[x]) {
    if(!pre[i]) {
      G[x].pb(i);
      odl[i]=odl[x]+1;
      DFS(i);
      ile[x]+=ile[i];
    } else if(pre[i]<pre[x]) P[x].pb(i);
  }
}
void DFS2(int x, int k) {
  if(!S[k].st || ans[x]) return;
  ans[x]=S[k].nd;
  --S[k].st;
  for(auto i : G[x]) DFS2(i, k);
}
void DFS3(int x, int k) {
  if(x==k) return;
  ans[x]=S[1].nd;
  --S[1].st;
  for(auto i : G[x]) DFS3(i, k);
}
void DFS5(int x) {
  if(!S[1].st) return;
  --S[1].st;
  ans[x]=S[1].nd;
  for(auto i : G[x]) DFS5(i);
}
void DFS4(int x, int k) {
  if(!S[1].st) return;
  for(auto i : P[x]) if(odl[i]<k) {
    DFS5(i);
    return;
  }
  for(auto i : G[x]) DFS4(i, k);
}
void DFS6(int x) {
  if(!S[0].st || ans[x]) return;
  --S[0].st;
  ans[x]=S[0].nd;
  for(auto i : G[x]) DFS6(i);
}
vector<int>find_split(int n, int a, int b, int c, vector<int>p, vector<int>q) {
  rep(i, n) ans.pb(0);
  S.pb({a, 1});
  S.pb({b, 2});
  S.pb({c, 3});
  sort(all(S));
  rep(i, p.size()) {
    V[p[i]].pb(q[i]);
    V[q[i]].pb(p[i]);
  }
  DFS(0);
  rep(j, 2) {
    rep(i, n) if(ile[i]>=S[0].st && n-ile[i]>=S[1].st) {
      DFS2(i, 0);
      DFS2(0, 1);
      rep(l, n) if(!ans[l]) ans[l]=S[2].nd;
      return ans;
    }
    swap(S[0], S[1]);
  }
  pair<int,int>mi={n, n};
  rep(i, n) if(ile[i]>=S[0].st) mi=min(mi, {ile[i], i});
  DFS3(0, mi.nd);
  for(auto i : G[mi.nd]) DFS4(i, odl[mi.nd]);
  if(S[1].st) {
    rep(i, n) ans[i]=0;
    return ans;
  }
  while(ans[mi.nd]) {
    ++S[0].st;
  }
  DFS6(mi.nd);
  rep(i, n) if(!ans[i]) ans[i]=S[2].nd;
  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:5:36: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    5 | #define rep(a, b) for(int a = 0; a < (b); ++a)
      |                                    ^
split.cpp:64:3: note: in expansion of macro 'rep'
   64 |   rep(i, p.size()) {
      |   ^~~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8280 KB ok, correct split
2 Correct 2 ms 8284 KB ok, correct split
3 Correct 2 ms 8284 KB ok, correct split
4 Correct 2 ms 8280 KB ok, correct split
5 Correct 2 ms 8284 KB ok, correct split
6 Correct 2 ms 8284 KB ok, correct split
7 Correct 67 ms 29188 KB ok, correct split
8 Correct 63 ms 26568 KB ok, correct split
9 Correct 80 ms 25700 KB ok, correct split
10 Correct 71 ms 29640 KB ok, correct split
11 Correct 67 ms 29640 KB ok, correct split

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8280 KB ok, correct split
2 Correct 2 ms 8284 KB ok, correct split
3 Correct 2 ms 8284 KB ok, correct split
4 Correct 76 ms 24628 KB ok, correct split
5 Correct 60 ms 18864 KB ok, correct split
6 Correct 71 ms 29612 KB ok, correct split
7 Correct 75 ms 26264 KB ok, correct split
8 Correct 85 ms 21636 KB ok, correct split
9 Correct 61 ms 20388 KB ok, correct split
10 Correct 43 ms 17832 KB ok, correct split
11 Correct 40 ms 17872 KB ok, correct split
12 Correct 41 ms 17876 KB ok, correct split

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8284 KB ok, correct split
2 Correct 58 ms 18856 KB ok, correct split
3 Correct 19 ms 12760 KB ok, correct split
4 Correct 2 ms 8280 KB ok, correct split
5 Correct 84 ms 23432 KB ok, correct split
6 Correct 70 ms 22992 KB ok, correct split
7 Correct 65 ms 22856 KB ok, correct split
8 Correct 63 ms 24520 KB ok, correct split
9 Correct 66 ms 22728 KB ok, correct split
10 Correct 20 ms 11988 KB ok, no valid answer
11 Correct 24 ms 13768 KB ok, no valid answer
12 Correct 49 ms 18388 KB ok, no valid answer
13 Correct 55 ms 18756 KB ok, no valid answer
14 Correct 39 ms 17864 KB ok, no valid answer

Subtask #4
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8284 KB ok, correct split
2 Correct 2 ms 8284 KB ok, no valid answer
3 Correct 2 ms 8284 KB ok, correct split
4 Correct 2 ms 8284 KB ok, correct split
5 Correct 2 ms 8284 KB ok, correct split
6 Correct 2 ms 8284 KB ok, correct split
7 Correct 2 ms 8284 KB ok, correct split
8 Correct 2 ms 8284 KB ok, correct split
9 Correct 4 ms 8796 KB ok, correct split
10 Correct 4 ms 8796 KB ok, correct split
11 Correct 3 ms 8284 KB ok, correct split
12 Correct 4 ms 8796 KB ok, correct split
13 Correct 2 ms 8284 KB ok, correct split
14 Correct 2 ms 8284 KB ok, correct split
15 Correct 2 ms 8284 KB ok, correct split
16 Correct 2 ms 8284 KB ok, correct split
17 Correct 2 ms 8284 KB ok, correct split
18 Correct 2 ms 8284 KB ok, correct split
19 Correct 2 ms 8540 KB ok, correct split
20 Correct 3 ms 8540 KB ok, correct split
21 Correct 3 ms 8796 KB ok, correct split
22 Correct 3 ms 8796 KB ok, correct split
23 Correct 3 ms 8724 KB ok, correct split
24 Correct 3 ms 8880 KB ok, correct split
25 Correct 4 ms 8796 KB ok, correct split
26 Execution timed out 2029 ms 8536 KB Time limit exceeded
27 Halted 0 ms 0 KB -

Subtask #5
0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8280 KB ok, correct split
2 Correct 2 ms 8284 KB ok, correct split
3 Correct 2 ms 8284 KB ok, correct split
4 Correct 2 ms 8280 KB ok, correct split
5 Correct 2 ms 8284 KB ok, correct split
6 Correct 2 ms 8284 KB ok, correct split
7 Correct 67 ms 29188 KB ok, correct split
8 Correct 63 ms 26568 KB ok, correct split
9 Correct 80 ms 25700 KB ok, correct split
10 Correct 71 ms 29640 KB ok, correct split
11 Correct 67 ms 29640 KB ok, correct split
12 Correct 2 ms 8280 KB ok, correct split
13 Correct 2 ms 8284 KB ok, correct split
14 Correct 2 ms 8284 KB ok, correct split
15 Correct 76 ms 24628 KB ok, correct split
16 Correct 60 ms 18864 KB ok, correct split
17 Correct 71 ms 29612 KB ok, correct split
18 Correct 75 ms 26264 KB ok, correct split
19 Correct 85 ms 21636 KB ok, correct split
20 Correct 61 ms 20388 KB ok, correct split
21 Correct 43 ms 17832 KB ok, correct split
22 Correct 40 ms 17872 KB ok, correct split
23 Correct 41 ms 17876 KB ok, correct split
24 Correct 2 ms 8284 KB ok, correct split
25 Correct 58 ms 18856 KB ok, correct split
26 Correct 19 ms 12760 KB ok, correct split
27 Correct 2 ms 8280 KB ok, correct split
28 Correct 84 ms 23432 KB ok, correct split
29 Correct 70 ms 22992 KB ok, correct split
30 Correct 65 ms 22856 KB ok, correct split
31 Correct 63 ms 24520 KB ok, correct split
32 Correct 66 ms 22728 KB ok, correct split
33 Correct 20 ms 11988 KB ok, no valid answer
34 Correct 24 ms 13768 KB ok, no valid answer
35 Correct 49 ms 18388 KB ok, no valid answer
36 Correct 55 ms 18756 KB ok, no valid answer
37 Correct 39 ms 17864 KB ok, no valid answer
38 Correct 2 ms 8284 KB ok, correct split
39 Correct 2 ms 8284 KB ok, no valid answer
40 Correct 2 ms 8284 KB ok, correct split
41 Correct 2 ms 8284 KB ok, correct split
42 Correct 2 ms 8284 KB ok, correct split
43 Correct 2 ms 8284 KB ok, correct split
44 Correct 2 ms 8284 KB ok, correct split
45 Correct 2 ms 8284 KB ok, correct split
46 Correct 4 ms 8796 KB ok, correct split
47 Correct 4 ms 8796 KB ok, correct split
48 Correct 3 ms 8284 KB ok, correct split
49 Correct 4 ms 8796 KB ok, correct split
50 Correct 2 ms 8284 KB ok, correct split
51 Correct 2 ms 8284 KB ok, correct split
52 Correct 2 ms 8284 KB ok, correct split
53 Correct 2 ms 8284 KB ok, correct split
54 Correct 2 ms 8284 KB ok, correct split
55 Correct 2 ms 8284 KB ok, correct split
56 Correct 2 ms 8540 KB ok, correct split
57 Correct 3 ms 8540 KB ok, correct split
58 Correct 3 ms 8796 KB ok, correct split
59 Correct 3 ms 8796 KB ok, correct split
60 Correct 3 ms 8724 KB ok, correct split
61 Correct 3 ms 8880 KB ok, correct split
62 Correct 4 ms 8796 KB ok, correct split
63 Execution timed out 2029 ms 8536 KB Time limit exceeded
64 Halted 0 ms 0 KB -