oj.uz

Submission #880183

# Submission time Handle Problem Language Result Execution time Memory
880183 2023-11-29T02:05:41 Z abcvuitunggio Parachute rings (IOI12_rings) C++17
37 / 100
 1309 ms 110036 KB 
#include <vector>
using namespace std;
int n,focused=-1,ch[5],cnt,mx,deg[1000001],deg2[1000001],p[1000001][5],cycle,cyclesize,sz[1000001][5];
vector <int> candidates,ke[1000001];
vector <pair <int, int>> edge;
void reset(int j){
    for (int i=0;i<n;i++){
        p[i][j]=i;
        sz[i][j]=1;
    }
    ch[j]=1;
}
int f(int i, int j){
    return (p[i][j]==i?i:p[i][j]=f(p[i][j],j));
}
bool unite(int u, int v, int idx){
    u=f(u,idx);
    v=f(v,idx);
    if (u==v)
        return 0;
    if (sz[u][idx]<sz[v][idx])
        swap(u,v);
    sz[u][idx]+=sz[v][idx];
    p[v][idx]=u;
    return 1;
}
void focus(int node, int j=0){
    reset(j);
    if (focused!=-1)
        for (int i=0;i<n;i++)
            deg[i]=0;
    for (auto [u,v]:edge)
        if (u!=node&&v!=node){
            ch[j]&=unite(u,v,j);
            if (focused!=-1){
                deg[u]++;
                deg[v]++;
                if (max(u,v)>2)
                    ch[j]=0;
            }
        }
}
void Init(int N){
    n=N;
    for (int i=0;i<5;i++)
        reset(i);
}
void Link(int a, int b){
    edge.push_back({a,b});
    if (focused!=-1){
        if (a!=focused&&b!=focused){
            ch[0]&=unite(a,b,0);
            deg[a]++;
            deg[b]++;
            if (max(deg[a],deg[b])>2)
                ch[0]=0;
        }
        return;
    }
    deg[a]++;
    deg[b]++;
    ke[a].push_back(b);
    ke[b].push_back(a);
    if (deg[a]==4){
        focus(a);
        focused=a;
        return;
    }
    if (deg[b]==4){
        focus(b);
        focused=b;
        return;
    }
    int cnt2=cnt;
    if (deg[a]==3){
        cnt2++;
        for (int v:ke[a])
            if (deg[v]>2&&v!=b){
                deg2[a]++;
                deg2[v]++;
            }
    }
    if (deg[b]==3){
        cnt2++;
        for (int v:ke[b])
            if (deg[v]>2){
                deg2[b]++;
                deg2[v]++;
            }
    }
    if (cnt2>4){
        cnt=cnt2;
        return;
    }
    if (!cnt2){
        if (deg[a]==2&&deg[b]==2&&f(a,0)==f(b,0)){
            cycle++;
            cyclesize=sz[f(a,0)][0];
        }
        unite(a,b,0);
    }
    else if (cnt2==1){
        if (!cnt){
            if (deg[a]<deg[b])
                swap(a,b);
            candidates.push_back(a);
            for (int v:ke[a])
                candidates.push_back(v);
            for (int i=0;i<candidates.size();i++)
                focus(candidates[i],i);
        }
        else{
            for (int i=0;i<candidates.size();i++)
                if (a!=candidates[i]&&b!=candidates[i])
                    ch[i]&=unite(a,b,i);
        }
    }
    else if (cnt2==2){
        if (cnt<2){
            candidates.clear();
            int u=-1,v=-1;
            for (int i=0;i<n;i++)
                if (deg[i]>2)
                    (u==-1?u=i:v=i);
            for (int i=0;i<n;i++){
                int cnt3=(i==u||i==v);
                for (int j:ke[i])
                    cnt3+=(j==u||j==v);
                if (cnt3==2)
                    candidates.push_back(i);
            }
            for (int i=0;i<candidates.size();i++)
                focus(candidates[i],i);
        }
        else{
            for (int i=0;i<candidates.size();i++)
                if (a!=candidates[i]&&b!=candidates[i])
                    ch[i]&=unite(a,b,i);
        }
    }
    else if (cnt<cnt2){
        candidates.clear();
        for (int i=0;i<n;i++)
            if (deg[i]>2&&deg2[i]==cnt2-1)
                candidates.push_back(i);
        for (int i=0;i<candidates.size();i++)
                focus(candidates[i],i);
    }
    else{
        for (int i=0;i<candidates.size();i++)
            if (a!=candidates[i]&&b!=candidates[i])
                ch[i]&=unite(a,b,i);
    }
    cnt=cnt2;
}
int CountCritical(){
    if (focused!=-1)
        return ch[0];
    if (cnt>4)
        return 0;
    if (cnt){
        int res=0;
        for (int i=0;i<candidates.size();i++)
            res+=ch[i];
        return res;
    }
    return (cycle>1?0:(cycle==1?cyclesize:n));
}

Compilation message

rings.cpp: In function 'void Link(int, int)':
rings.cpp:109:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  109 |             for (int i=0;i<candidates.size();i++)
      |                          ~^~~~~~~~~~~~~~~~~~
rings.cpp:113:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  113 |             for (int i=0;i<candidates.size();i++)
      |                          ~^~~~~~~~~~~~~~~~~~
rings.cpp:132:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  132 |             for (int i=0;i<candidates.size();i++)
      |                          ~^~~~~~~~~~~~~~~~~~
rings.cpp:136:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  136 |             for (int i=0;i<candidates.size();i++)
      |                          ~^~~~~~~~~~~~~~~~~~
rings.cpp:146:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  146 |         for (int i=0;i<candidates.size();i++)
      |                      ~^~~~~~~~~~~~~~~~~~
rings.cpp:150:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  150 |         for (int i=0;i<candidates.size();i++)
      |                      ~^~~~~~~~~~~~~~~~~~
rings.cpp: In function 'int CountCritical()':
rings.cpp:163:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  163 |         for (int i=0;i<candidates.size();i++)
      |                      ~^~~~~~~~~~~~~~~~~~

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 27996 KB Output is correct
2 Correct 7 ms 28252 KB Output is correct
3 Correct 8 ms 28252 KB Output is correct
4 Correct 8 ms 28172 KB Output is correct
5 Correct 7 ms 28092 KB Output is correct
6 Correct 8 ms 28504 KB Output is correct
7 Correct 6 ms 27996 KB Output is correct
8 Correct 7 ms 28252 KB Output is correct
9 Correct 8 ms 30404 KB Output is correct
10 Correct 7 ms 28248 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 296 ms 71096 KB Output is correct
2 Correct 574 ms 87656 KB Output is correct
3 Correct 446 ms 80320 KB Output is correct
4 Correct 884 ms 110036 KB Output is correct
5 Correct 885 ms 109936 KB Output is correct
6 Correct 863 ms 106508 KB Output is correct
7 Correct 423 ms 82368 KB Output is correct
8 Correct 1212 ms 107252 KB Output is correct
9 Correct 1309 ms 109864 KB Output is correct
10 Correct 581 ms 107692 KB Output is correct

Subtask #3
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 27996 KB Output is correct
2 Correct 7 ms 28252 KB Output is correct
3 Correct 8 ms 28252 KB Output is correct
4 Correct 8 ms 28172 KB Output is correct
5 Correct 7 ms 28092 KB Output is correct
6 Correct 8 ms 28504 KB Output is correct
7 Correct 6 ms 27996 KB Output is correct
8 Correct 7 ms 28252 KB Output is correct
9 Correct 8 ms 30404 KB Output is correct
10 Correct 7 ms 28248 KB Output is correct
11 Correct 8 ms 30296 KB Output is correct
12 Correct 10 ms 32604 KB Output is correct
13 Incorrect 10 ms 32452 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 27996 KB Output is correct
2 Correct 7 ms 28252 KB Output is correct
3 Correct 8 ms 28252 KB Output is correct
4 Correct 8 ms 28172 KB Output is correct
5 Correct 7 ms 28092 KB Output is correct
6 Correct 8 ms 28504 KB Output is correct
7 Correct 6 ms 27996 KB Output is correct
8 Correct 7 ms 28252 KB Output is correct
9 Correct 8 ms 30404 KB Output is correct
10 Correct 7 ms 28248 KB Output is correct
11 Correct 8 ms 30296 KB Output is correct
12 Correct 10 ms 32604 KB Output is correct
13 Incorrect 10 ms 32452 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #5
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 27996 KB Output is correct
2 Correct 7 ms 28252 KB Output is correct
3 Correct 8 ms 28252 KB Output is correct
4 Correct 8 ms 28172 KB Output is correct
5 Correct 7 ms 28092 KB Output is correct
6 Correct 8 ms 28504 KB Output is correct
7 Correct 6 ms 27996 KB Output is correct
8 Correct 7 ms 28252 KB Output is correct
9 Correct 8 ms 30404 KB Output is correct
10 Correct 7 ms 28248 KB Output is correct
11 Correct 296 ms 71096 KB Output is correct
12 Correct 574 ms 87656 KB Output is correct
13 Correct 446 ms 80320 KB Output is correct
14 Correct 884 ms 110036 KB Output is correct
15 Correct 885 ms 109936 KB Output is correct
16 Correct 863 ms 106508 KB Output is correct
17 Correct 423 ms 82368 KB Output is correct
18 Correct 1212 ms 107252 KB Output is correct
19 Correct 1309 ms 109864 KB Output is correct
20 Correct 581 ms 107692 KB Output is correct
21 Correct 8 ms 30296 KB Output is correct
22 Correct 10 ms 32604 KB Output is correct
23 Incorrect 10 ms 32452 KB Output isn't correct
24 Halted 0 ms 0 KB -