Submission #562485

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
562485	2022-05-14T13:17:53 Z	CaroLinda	Parachute rings (IOI12_rings)	C++14	100 / 100	2184 ms	75648 KB

rings

/*
SUBTASK 1 JUST TO TEST HIPHOTESES
*/

#include <bits/stdc++.h>
 
#define all(x) x.begin(),x.end()
#define sz(x) (int)(x.size())
 
const int MAXN = 1e6+10 ;
 
using namespace std ;
 
int N ;
vector<pair<int,int> > edg ;
int dsu[5][MAXN] , qtd[5][MAXN] , deg[5][MAXN] , qtdCycle[5] , sz_cycle[5] ;
int bigDegree[5] , guy[5] ;
 
int find(int x, int idx){
  return dsu[idx][x] = ( x == dsu[idx][x]) ? x : find(dsu[idx][x],idx) ;
}

int isCycle(int x, int y, int idx ){
  x = find(x,idx) ;
  y = find(y,idx) ;

  if(x == y  )return true ;

  if(rand() % 2) swap(x,y) ;

  dsu[idx][x] = y ;
  qtd[idx][y] += qtd[idx][x] ;

  return false ;
}

void addEdge(int A, int B, int idx){

  if(A == guy[idx] || B == guy[idx]) return ;

  bigDegree[idx] = max(bigDegree[idx],++deg[idx][A]) ;
  bigDegree[idx] = max(bigDegree[idx],++deg[idx][B]) ;

  if(isCycle(A,B,idx)){
    qtdCycle[idx]++ ;
    sz_cycle[idx] = qtd[idx][find(A,idx)] ;
  }

}

void Init(int N_) {
  N = N_;
  guy[0] = -1 ;
  sz_cycle[0] = N ;
  for(int i= 0 ; i < 5 ; i++ )
    for(int j = 0 ; j < N ; j++ ){
      qtd[i][j] = 1 ;
      dsu[i][j] = j ;
    }
}
 
void Link(int A, int B) {
  
  edg.push_back(make_pair(A,B)) ;
  bool spoiled = (bigDegree[0] >= 3) ;
 
  addEdge(A,B,0) ;
  if(spoiled)
    for(int i = 1 ; i < 5 ; i++ ) addEdge(A,B,i) ;

  if(deg[0][A] < deg[0][B]) swap(A,B) ;
  if(bigDegree[0] < 3 || spoiled ) return ;

  guy[1] = A ;
  int id = 1 ;
  for(auto &e : edg ){
    if(e.first == A ) swap(e.first, e.second );
    if(e.second == A) guy[++id] = e.first ;
  }

  for(auto &e : edg )
    for(int i = 1 ;i  < 5 ; i++ )
      addEdge(e.first, e.second , i ) ;
}
 
int CountCritical() {

  int ans = 0 ;
  if(bigDegree[0] < 3 && qtdCycle[0] <= 1){
    ans += sz_cycle[0] ;
  }

  if(bigDegree[0] >= 3 ){
    for(int i = 1 ; i < 5 ; i++ ) 
      ans += (bigDegree[i] < 3 && qtdCycle[i] == 0 ) ;
  }

  return ans ;

}

Subtask #1
20.0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	312 KB	Output is correct
2	Correct	2 ms	732 KB	Output is correct
3	Correct	3 ms	852 KB	Output is correct
4	Correct	1 ms	340 KB	Output is correct
5	Correct	1 ms	596 KB	Output is correct
6	Correct	2 ms	724 KB	Output is correct
7	Correct	1 ms	700 KB	Output is correct
8	Correct	2 ms	596 KB	Output is correct
9	Correct	3 ms	852 KB	Output is correct
10	Correct	3 ms	852 KB	Output is correct

Subtask #2
17.0 / 17.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	223 ms	28980 KB	Output is correct
2	Correct	1223 ms	57760 KB	Output is correct
3	Correct	2184 ms	71032 KB	Output is correct
4	Correct	499 ms	53892 KB	Output is correct
5	Correct	491 ms	55232 KB	Output is correct
6	Correct	488 ms	54420 KB	Output is correct
7	Correct	1989 ms	70880 KB	Output is correct
8	Correct	1398 ms	66372 KB	Output is correct
9	Correct	1505 ms	70724 KB	Output is correct
10	Correct	369 ms	55096 KB	Output is correct

Subtask #3
18.0 / 18.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	312 KB	Output is correct
2	Correct	2 ms	732 KB	Output is correct
3	Correct	3 ms	852 KB	Output is correct
4	Correct	1 ms	340 KB	Output is correct
5	Correct	1 ms	596 KB	Output is correct
6	Correct	2 ms	724 KB	Output is correct
7	Correct	1 ms	700 KB	Output is correct
8	Correct	2 ms	596 KB	Output is correct
9	Correct	3 ms	852 KB	Output is correct
10	Correct	3 ms	852 KB	Output is correct
11	Correct	3 ms	852 KB	Output is correct
12	Correct	5 ms	1364 KB	Output is correct
13	Correct	6 ms	1364 KB	Output is correct
14	Correct	6 ms	1132 KB	Output is correct
15	Correct	5 ms	1748 KB	Output is correct
16	Correct	3 ms	1092 KB	Output is correct
17	Correct	4 ms	1364 KB	Output is correct
18	Correct	5 ms	1876 KB	Output is correct
19	Correct	3 ms	1108 KB	Output is correct
20	Correct	5 ms	1364 KB	Output is correct

Subtask #4
14.0 / 14.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	312 KB	Output is correct
2	Correct	2 ms	732 KB	Output is correct
3	Correct	3 ms	852 KB	Output is correct
4	Correct	1 ms	340 KB	Output is correct
5	Correct	1 ms	596 KB	Output is correct
6	Correct	2 ms	724 KB	Output is correct
7	Correct	1 ms	700 KB	Output is correct
8	Correct	2 ms	596 KB	Output is correct
9	Correct	3 ms	852 KB	Output is correct
10	Correct	3 ms	852 KB	Output is correct
11	Correct	3 ms	852 KB	Output is correct
12	Correct	5 ms	1364 KB	Output is correct
13	Correct	6 ms	1364 KB	Output is correct
14	Correct	6 ms	1132 KB	Output is correct
15	Correct	5 ms	1748 KB	Output is correct
16	Correct	3 ms	1092 KB	Output is correct
17	Correct	4 ms	1364 KB	Output is correct
18	Correct	5 ms	1876 KB	Output is correct
19	Correct	3 ms	1108 KB	Output is correct
20	Correct	5 ms	1364 KB	Output is correct
21	Correct	12 ms	3416 KB	Output is correct
22	Correct	18 ms	5292 KB	Output is correct
23	Correct	30 ms	6336 KB	Output is correct
24	Correct	61 ms	7248 KB	Output is correct
25	Correct	17 ms	6708 KB	Output is correct
26	Correct	43 ms	7612 KB	Output is correct
27	Correct	27 ms	6224 KB	Output is correct
28	Correct	49 ms	7752 KB	Output is correct
29	Correct	45 ms	7452 KB	Output is correct
30	Correct	31 ms	6768 KB	Output is correct

Subtask #5
31.0 / 31.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	312 KB	Output is correct
2	Correct	2 ms	732 KB	Output is correct
3	Correct	3 ms	852 KB	Output is correct
4	Correct	1 ms	340 KB	Output is correct
5	Correct	1 ms	596 KB	Output is correct
6	Correct	2 ms	724 KB	Output is correct
7	Correct	1 ms	700 KB	Output is correct
8	Correct	2 ms	596 KB	Output is correct
9	Correct	3 ms	852 KB	Output is correct
10	Correct	3 ms	852 KB	Output is correct
11	Correct	223 ms	28980 KB	Output is correct
12	Correct	1223 ms	57760 KB	Output is correct
13	Correct	2184 ms	71032 KB	Output is correct
14	Correct	499 ms	53892 KB	Output is correct
15	Correct	491 ms	55232 KB	Output is correct
16	Correct	488 ms	54420 KB	Output is correct
17	Correct	1989 ms	70880 KB	Output is correct
18	Correct	1398 ms	66372 KB	Output is correct
19	Correct	1505 ms	70724 KB	Output is correct
20	Correct	369 ms	55096 KB	Output is correct
21	Correct	3 ms	852 KB	Output is correct
22	Correct	5 ms	1364 KB	Output is correct
23	Correct	6 ms	1364 KB	Output is correct
24	Correct	6 ms	1132 KB	Output is correct
25	Correct	5 ms	1748 KB	Output is correct
26	Correct	3 ms	1092 KB	Output is correct
27	Correct	4 ms	1364 KB	Output is correct
28	Correct	5 ms	1876 KB	Output is correct
29	Correct	3 ms	1108 KB	Output is correct
30	Correct	5 ms	1364 KB	Output is correct
31	Correct	12 ms	3416 KB	Output is correct
32	Correct	18 ms	5292 KB	Output is correct
33	Correct	30 ms	6336 KB	Output is correct
34	Correct	61 ms	7248 KB	Output is correct
35	Correct	17 ms	6708 KB	Output is correct
36	Correct	43 ms	7612 KB	Output is correct
37	Correct	27 ms	6224 KB	Output is correct
38	Correct	49 ms	7752 KB	Output is correct
39	Correct	45 ms	7452 KB	Output is correct
40	Correct	31 ms	6768 KB	Output is correct
41	Correct	134 ms	29304 KB	Output is correct
42	Correct	578 ms	62336 KB	Output is correct
43	Correct	277 ms	60472 KB	Output is correct
44	Correct	1010 ms	73940 KB	Output is correct
45	Correct	1295 ms	75648 KB	Output is correct
46	Correct	396 ms	54600 KB	Output is correct
47	Correct	460 ms	55584 KB	Output is correct
48	Correct	579 ms	69916 KB	Output is correct
49	Correct	375 ms	61752 KB	Output is correct
50	Correct	368 ms	60712 KB	Output is correct
51	Correct	334 ms	52904 KB	Output is correct
52	Correct	975 ms	60152 KB	Output is correct
53	Correct	581 ms	69216 KB	Output is correct
54	Correct	1248 ms	65916 KB	Output is correct
55	Correct	1364 ms	71312 KB	Output is correct

Submission #562485

Compilation message

Subtask #1 20.0 / 20.0

Subtask #2 17.0 / 17.0

Subtask #3 18.0 / 18.0

Subtask #4 14.0 / 14.0

Subtask #5 31.0 / 31.0

Subtask #1
20.0 / 20.0

Subtask #2
17.0 / 17.0

Subtask #3
18.0 / 18.0

Subtask #4
14.0 / 14.0

Subtask #5
31.0 / 31.0