oj.uz

Submission #120445

# Submission time Handle Problem Language Result Execution time Memory
120445 2019-06-24T13:37:41 Z nvmdava Parachute rings (IOI12_rings) C++17
37 / 100
 2720 ms 201704 KB 
#include <bits/stdc++.h>
#define ff first
#define ss second
using namespace std;

vector<pair<int, int> > con;
vector<int> adj[1000005];
set<int> pos, t;
int N;
int p[1000005][3];
void Init(int N_) {
  N = N_;
  for(int i = 0; i < N; i++)
   for(int j = 0; j < 3; j++)
      p[i][j] = i;
   for(int i = 0; i < N; i++)
      pos.insert(i);
}
int put = 0;
int v[3];

int find(int v, int i){
   if(v == p[v][i]) return v;
   return p[v][i] = find(p[v][i], i);
}

bool merge(int v, int u, int i){
   if(i){
      if(v == ::v[i]) return 0;
      if(u == ::v[i]) return 0;
   }
   v = find(v, i);
   u = find(u, i);
   if(v == u) return 1;
   p[v][i] = u;
   return 0;
}

bool dfs(int A, int B){
   t.insert(A);
   for(int x : adj[A]){
      if(x == B) continue;
      if(t.count(x)) return 1;
      if(dfs(x, A)) return 1;
   }
   t.erase(A);
   return 0;
}

void Link(int A, int B){
   if(pos.empty()) return;
   adj[A].push_back(B);
   adj[B].push_back(A);
   t.clear();
   if(adj[A].size() == 4){
      if(pos.count(A))
         t.insert(A);
      swap(t, pos);
      t.clear();
   } else if(adj[A].size() == 3){
      if(pos.count(A))
         t.insert(A);
      for(int x : adj[A])
         if(pos.count(x))
            t.insert(x);
      swap(t, pos);
      t.clear();
   }
   if(adj[B].size() == 4){
      if(pos.count(B))
         t.insert(B);
      swap(t, pos);
      t.clear();
   } else if(adj[B].size() == 3){
      if(pos.count(B))
         t.insert(B);
      for(int x : adj[B])
         if(pos.count(x))
            t.insert(x);
      swap(t, pos);
      t.clear();
   }
   if(put == 0 && pos.size() <= 2){
      for(int x : pos){
         v[put++] = x;
      }
      for(auto x : con){
         if(merge(x.ff, x.ss, 1)) v[1] = -1;
         if(merge(x.ff, x.ss, 2)) v[2] = -1;
      }
   }
   con.push_back({A, B});
   if(put){
      if(merge(A, B, 1)) v[1] = -1;
      if(merge(A, B, 2)) v[2] = -1;
      pos.clear();
      if(v[1] > -1) pos.insert(v[1]);
      if(v[2] > -1) pos.insert(v[2]);
      return;
   }
   if(pos.empty()) return;
   if(merge(A, B, 0) == 0 || put) return;
   dfs(A, B);
   set<int> lol;
   for(int x : t)
      if(pos.count(x))
         lol.insert(x);
   swap(lol, pos);
   t.clear();
}

int CountCritical() {
  return pos.size();
}

Compilation message

rings.cpp: In function 'void Init(int)':
rings.cpp:13:3: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   for(int i = 0; i < N; i++)
   ^~~
rings.cpp:16:4: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
    for(int i = 0; i < N; i++)
    ^~~

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 23808 KB Output is correct
2 Correct 26 ms 24320 KB Output is correct
3 Correct 26 ms 24192 KB Output is correct
4 Correct 23 ms 23880 KB Output is correct
5 Correct 25 ms 24320 KB Output is correct
6 Correct 29 ms 24824 KB Output is correct
7 Correct 24 ms 24064 KB Output is correct
8 Correct 26 ms 24320 KB Output is correct
9 Correct 26 ms 24320 KB Output is correct
10 Correct 25 ms 24320 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 607 ms 81612 KB Output is correct
2 Correct 1552 ms 96060 KB Output is correct
3 Correct 574 ms 95876 KB Output is correct
4 Correct 1679 ms 135168 KB Output is correct
5 Correct 1741 ms 137876 KB Output is correct
6 Correct 2720 ms 201704 KB Output is correct
7 Correct 590 ms 95464 KB Output is correct
8 Correct 1656 ms 125096 KB Output is correct
9 Correct 1774 ms 134320 KB Output is correct
10 Correct 1166 ms 132400 KB Output is correct

Subtask #3
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 23808 KB Output is correct
2 Correct 26 ms 24320 KB Output is correct
3 Correct 26 ms 24192 KB Output is correct
4 Correct 23 ms 23880 KB Output is correct
5 Correct 25 ms 24320 KB Output is correct
6 Correct 29 ms 24824 KB Output is correct
7 Correct 24 ms 24064 KB Output is correct
8 Correct 26 ms 24320 KB Output is correct
9 Correct 26 ms 24320 KB Output is correct
10 Correct 25 ms 24320 KB Output is correct
11 Incorrect 26 ms 24320 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 23808 KB Output is correct
2 Correct 26 ms 24320 KB Output is correct
3 Correct 26 ms 24192 KB Output is correct
4 Correct 23 ms 23880 KB Output is correct
5 Correct 25 ms 24320 KB Output is correct
6 Correct 29 ms 24824 KB Output is correct
7 Correct 24 ms 24064 KB Output is correct
8 Correct 26 ms 24320 KB Output is correct
9 Correct 26 ms 24320 KB Output is correct
10 Correct 25 ms 24320 KB Output is correct
11 Incorrect 26 ms 24320 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #5
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 23808 KB Output is correct
2 Correct 26 ms 24320 KB Output is correct
3 Correct 26 ms 24192 KB Output is correct
4 Correct 23 ms 23880 KB Output is correct
5 Correct 25 ms 24320 KB Output is correct
6 Correct 29 ms 24824 KB Output is correct
7 Correct 24 ms 24064 KB Output is correct
8 Correct 26 ms 24320 KB Output is correct
9 Correct 26 ms 24320 KB Output is correct
10 Correct 25 ms 24320 KB Output is correct
11 Correct 607 ms 81612 KB Output is correct
12 Correct 1552 ms 96060 KB Output is correct
13 Correct 574 ms 95876 KB Output is correct
14 Correct 1679 ms 135168 KB Output is correct
15 Correct 1741 ms 137876 KB Output is correct
16 Correct 2720 ms 201704 KB Output is correct
17 Correct 590 ms 95464 KB Output is correct
18 Correct 1656 ms 125096 KB Output is correct
19 Correct 1774 ms 134320 KB Output is correct
20 Correct 1166 ms 132400 KB Output is correct
21 Incorrect 26 ms 24320 KB Output isn't correct
22 Halted 0 ms 0 KB -