oj.uz

Submission #231915

# Submission time Handle Problem Language Result Execution time Memory
231915 2020-05-15T09:48:23 Z AlexLuchianov Parachute rings (IOI12_rings) C++14
100 / 100
 2320 ms 146880 KB 
#include <iostream>
#include <vector>
#include <algorithm>

int const nmax = 1000000;

struct Dsu{
  std::vector<int> mult;
  std::vector<int> sz;

  Dsu(int n = 0){
    mult.resize(1 + n);
    sz.resize(1 + n);
    for(int i = 1;i <= n; i++) {
      mult[i] = i;
      sz[i] = 1;
    }
  }

  int jump(int gala){
    if(mult[gala] != gala)
      mult[gala] = jump(mult[gala]);
    return mult[gala];
  }

  void unite(int gala, int galb){
    gala = jump(gala);
    galb = jump(galb);
    if(gala == galb)
      return ;
    if(sz[galb] < sz[gala])
      std::swap(gala, galb);
    sz[galb] += sz[gala];
    mult[gala] = galb;
  }

  int getsize(int gala){
    return sz[jump(gala)];
  }

  bool connected(int gala, int galb){
    return (jump(gala) == jump(galb));
  }
};

struct Ring{
  int avoid;
  std::vector<int> grade;
  int iscycle, isgreat;
  int cyclesize = 0;

  int n;
  Dsu mp;

  Ring(int n_ = 0, int avoid_ = 0){
    n = n_;
    grade.resize(1 + n);
    avoid = avoid_;
    iscycle = isgreat = 0;
    mp = Dsu(n);
  }

  void unite(int gala, int galb){
    if(gala == avoid || galb == avoid)
      return ;
    if(mp.connected(gala, galb) == 1) {
      iscycle++;
      cyclesize = mp.getsize(gala);
    }

    mp.unite(gala, galb);
    grade[gala]++;
    grade[galb]++;
    if(grade[gala] == 3 || grade[galb] == 3)
      isgreat = 1;
  }

  bool valid(){
    return ((0 == iscycle) && (0 == isgreat));
  }
};


int N, phase = 1;
Ring universal;
int result;

void Init(int N_) {
  N = N_;
  result = N;
  universal = Ring(N, 0);
}


std::vector<std::pair<int,int>> edges;
std::vector<int> g[1 + nmax];
std::vector<std::pair<int,Ring> > cand;


void Link(int a, int b) {
  ++a;
  ++b;
  edges.push_back({a, b});
  g[a].push_back(b);
  g[b].push_back(a);

  universal.unite(a, b);

  if(phase < 3 && universal.isgreat == 1){
    phase = 3;
    std::vector<int> temp;
    for(int h = 0; h < g[a].size(); h++)
      temp.push_back(g[a][h]);
    for(int h = 0; h < g[b].size(); h++)
      temp.push_back(g[b][h]);
    std::sort(temp.begin(), temp.end());
    temp.erase(unique(temp.begin(), temp.end()), temp.end());

    for(int i = 0; i < temp.size(); i++){
      cand.push_back({temp[i], Ring(N, temp[i])});
      for(int j = 0; j < edges.size(); j++)
        cand[i].second.unite(edges[j].first, edges[j].second);
    }

  } else if(phase == 3){
    for(int i = 0; i < cand.size(); i++)
      cand[i].second.unite(a, b);
  } else if(1 < universal.iscycle){
    result = 0;
  } else if(phase == 1 && 1 == universal.iscycle){
    phase = 2;
    result = universal.cyclesize;
  }
}

int CountCritical() {
  if(phase < 3)
    return result;
  else {
    result = 0;
    for(int i = 0; i < cand.size(); i++)
      result += cand[i].second.valid();
    return result;
  }
}

Compilation message

rings.cpp: In function 'void Link(int, int)':
rings.cpp:112:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int h = 0; h < g[a].size(); h++)
                    ~~^~~~~~~~~~~~~
rings.cpp:114:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int h = 0; h < g[b].size(); h++)
                    ~~^~~~~~~~~~~~~
rings.cpp:119:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0; i < temp.size(); i++){
                    ~~^~~~~~~~~~~~~
rings.cpp:121:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       for(int j = 0; j < edges.size(); j++)
                      ~~^~~~~~~~~~~~~~
rings.cpp:126:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0; i < cand.size(); i++)
                    ~~^~~~~~~~~~~~~
rings.cpp: In function 'int CountCritical()':
rings.cpp:141:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0; i < cand.size(); i++)
                    ~~^~~~~~~~~~~~~

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 23808 KB Output is correct
2 Correct 20 ms 24192 KB Output is correct
3 Correct 21 ms 24320 KB Output is correct
4 Correct 19 ms 23936 KB Output is correct
5 Correct 19 ms 23936 KB Output is correct
6 Correct 20 ms 24192 KB Output is correct
7 Correct 20 ms 24320 KB Output is correct
8 Correct 20 ms 24064 KB Output is correct
9 Correct 22 ms 24320 KB Output is correct
10 Correct 21 ms 24448 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 485 ms 57064 KB Output is correct
2 Correct 1755 ms 112912 KB Output is correct
3 Correct 2136 ms 129992 KB Output is correct
4 Correct 1247 ms 88252 KB Output is correct
5 Correct 1244 ms 88404 KB Output is correct
6 Correct 1200 ms 86432 KB Output is correct
7 Correct 2133 ms 128680 KB Output is correct
8 Correct 2320 ms 138948 KB Output is correct
9 Correct 2258 ms 146880 KB Output is correct
10 Correct 814 ms 85332 KB Output is correct

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 23808 KB Output is correct
2 Correct 20 ms 24192 KB Output is correct
3 Correct 21 ms 24320 KB Output is correct
4 Correct 19 ms 23936 KB Output is correct
5 Correct 19 ms 23936 KB Output is correct
6 Correct 20 ms 24192 KB Output is correct
7 Correct 20 ms 24320 KB Output is correct
8 Correct 20 ms 24064 KB Output is correct
9 Correct 22 ms 24320 KB Output is correct
10 Correct 21 ms 24448 KB Output is correct
11 Correct 24 ms 24448 KB Output is correct
12 Correct 26 ms 24960 KB Output is correct
13 Correct 25 ms 25088 KB Output is correct
14 Correct 25 ms 24704 KB Output is correct
15 Correct 24 ms 25344 KB Output is correct
16 Correct 24 ms 24576 KB Output is correct
17 Correct 28 ms 24960 KB Output is correct
18 Correct 27 ms 25720 KB Output is correct
19 Correct 25 ms 24576 KB Output is correct
20 Correct 25 ms 24960 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 23808 KB Output is correct
2 Correct 20 ms 24192 KB Output is correct
3 Correct 21 ms 24320 KB Output is correct
4 Correct 19 ms 23936 KB Output is correct
5 Correct 19 ms 23936 KB Output is correct
6 Correct 20 ms 24192 KB Output is correct
7 Correct 20 ms 24320 KB Output is correct
8 Correct 20 ms 24064 KB Output is correct
9 Correct 22 ms 24320 KB Output is correct
10 Correct 21 ms 24448 KB Output is correct
11 Correct 24 ms 24448 KB Output is correct
12 Correct 26 ms 24960 KB Output is correct
13 Correct 25 ms 25088 KB Output is correct
14 Correct 25 ms 24704 KB Output is correct
15 Correct 24 ms 25344 KB Output is correct
16 Correct 24 ms 24576 KB Output is correct
17 Correct 28 ms 24960 KB Output is correct
18 Correct 27 ms 25720 KB Output is correct
19 Correct 25 ms 24576 KB Output is correct
20 Correct 25 ms 24960 KB Output is correct
21 Correct 41 ms 26236 KB Output is correct
22 Correct 50 ms 27120 KB Output is correct
23 Correct 71 ms 27888 KB Output is correct
24 Correct 114 ms 31736 KB Output is correct
25 Correct 37 ms 30208 KB Output is correct
26 Correct 98 ms 32500 KB Output is correct
27 Correct 71 ms 28656 KB Output is correct
28 Correct 133 ms 33008 KB Output is correct
29 Correct 84 ms 31988 KB Output is correct
30 Correct 91 ms 29292 KB Output is correct

Subtask #5
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 23808 KB Output is correct
2 Correct 20 ms 24192 KB Output is correct
3 Correct 21 ms 24320 KB Output is correct
4 Correct 19 ms 23936 KB Output is correct
5 Correct 19 ms 23936 KB Output is correct
6 Correct 20 ms 24192 KB Output is correct
7 Correct 20 ms 24320 KB Output is correct
8 Correct 20 ms 24064 KB Output is correct
9 Correct 22 ms 24320 KB Output is correct
10 Correct 21 ms 24448 KB Output is correct
11 Correct 485 ms 57064 KB Output is correct
12 Correct 1755 ms 112912 KB Output is correct
13 Correct 2136 ms 129992 KB Output is correct
14 Correct 1247 ms 88252 KB Output is correct
15 Correct 1244 ms 88404 KB Output is correct
16 Correct 1200 ms 86432 KB Output is correct
17 Correct 2133 ms 128680 KB Output is correct
18 Correct 2320 ms 138948 KB Output is correct
19 Correct 2258 ms 146880 KB Output is correct
20 Correct 814 ms 85332 KB Output is correct
21 Correct 24 ms 24448 KB Output is correct
22 Correct 26 ms 24960 KB Output is correct
23 Correct 25 ms 25088 KB Output is correct
24 Correct 25 ms 24704 KB Output is correct
25 Correct 24 ms 25344 KB Output is correct
26 Correct 24 ms 24576 KB Output is correct
27 Correct 28 ms 24960 KB Output is correct
28 Correct 27 ms 25720 KB Output is correct
29 Correct 25 ms 24576 KB Output is correct
30 Correct 25 ms 24960 KB Output is correct
31 Correct 41 ms 26236 KB Output is correct
32 Correct 50 ms 27120 KB Output is correct
33 Correct 71 ms 27888 KB Output is correct
34 Correct 114 ms 31736 KB Output is correct
35 Correct 37 ms 30208 KB Output is correct
36 Correct 98 ms 32500 KB Output is correct
37 Correct 71 ms 28656 KB Output is correct
38 Correct 133 ms 33008 KB Output is correct
39 Correct 84 ms 31988 KB Output is correct
40 Correct 91 ms 29292 KB Output is correct
41 Correct 255 ms 43552 KB Output is correct
42 Correct 934 ms 109240 KB Output is correct
43 Correct 369 ms 85872 KB Output is correct
44 Correct 1412 ms 125140 KB Output is correct
45 Correct 1449 ms 117852 KB Output is correct
46 Correct 838 ms 78008 KB Output is correct
47 Correct 1070 ms 78984 KB Output is correct
48 Correct 903 ms 108184 KB Output is correct
49 Correct 795 ms 77012 KB Output is correct
50 Correct 842 ms 76612 KB Output is correct
51 Correct 522 ms 80236 KB Output is correct
52 Correct 1228 ms 106156 KB Output is correct
53 Correct 936 ms 108560 KB Output is correct
54 Correct 2086 ms 123780 KB Output is correct
55 Correct 2175 ms 122328 KB Output is correct