oj.uz

Submission #880177

# Submission time Handle Problem Language Result Execution time Memory
880177 2023-11-29T01:44:35 Z abcvuitunggio Parachute rings (IOI12_rings) C++17
0 / 100
 1444 ms 107848 KB 
#include <iostream>
#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 Init(int N){
    n=N;
    for (int i=0;i<5;i++)
        reset(i);
}
void focus(int node, int j=0){
    reset(j);
    for (auto [u,v]:edge)
        if (u!=node&&v!=node)
            ch[j]&=unite(u,v,j);
}
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);
        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);
            candidates.push_back(u);
            candidates.push_back(v);
            for (int i=0;i<n;i++){
                int cnt3=0;
                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:95:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   95 |             for (int i=0;i<candidates.size();i++)
      |                          ~^~~~~~~~~~~~~~~~~~
rings.cpp:99:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   99 |             for (int i=0;i<candidates.size();i++)
      |                          ~^~~~~~~~~~~~~~~~~~
rings.cpp:120:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  120 |             for (int i=0;i<candidates.size();i++)
      |                          ~^~~~~~~~~~~~~~~~~~
rings.cpp:124:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  124 |             for (int i=0;i<candidates.size();i++)
      |                          ~^~~~~~~~~~~~~~~~~~
rings.cpp:134:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  134 |         for (int i=0;i<candidates.size();i++)
      |                      ~^~~~~~~~~~~~~~~~~~
rings.cpp:138:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  138 |         for (int i=0;i<candidates.size();i++)
      |                      ~^~~~~~~~~~~~~~~~~~
rings.cpp: In function 'int CountCritical()':
rings.cpp:151:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  151 |         for (int i=0;i<candidates.size();i++)
      |                      ~^~~~~~~~~~~~~~~~~~

Subtask #1
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 29276 KB Output is correct
2 Correct 8 ms 29532 KB Output is correct
3 Correct 7 ms 29456 KB Output is correct
4 Correct 7 ms 29276 KB Output is correct
5 Correct 7 ms 29276 KB Output is correct
6 Correct 8 ms 29788 KB Output is correct
7 Correct 6 ms 29276 KB Output is correct
8 Correct 7 ms 29512 KB Output is correct
9 Correct 8 ms 31580 KB Output is correct
10 Incorrect 8 ms 29532 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 314 ms 72152 KB Output is correct
2 Correct 618 ms 86408 KB Output is correct
3 Correct 404 ms 78644 KB Output is correct
4 Correct 888 ms 107684 KB Output is correct
5 Correct 924 ms 107796 KB Output is correct
6 Correct 851 ms 106412 KB Output is correct
7 Correct 390 ms 78944 KB Output is correct
8 Correct 1177 ms 105808 KB Output is correct
9 Incorrect 1444 ms 107848 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #3
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 29276 KB Output is correct
2 Correct 8 ms 29532 KB Output is correct
3 Correct 7 ms 29456 KB Output is correct
4 Correct 7 ms 29276 KB Output is correct
5 Correct 7 ms 29276 KB Output is correct
6 Correct 8 ms 29788 KB Output is correct
7 Correct 6 ms 29276 KB Output is correct
8 Correct 7 ms 29512 KB Output is correct
9 Correct 8 ms 31580 KB Output is correct
10 Incorrect 8 ms 29532 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 29276 KB Output is correct
2 Correct 8 ms 29532 KB Output is correct
3 Correct 7 ms 29456 KB Output is correct
4 Correct 7 ms 29276 KB Output is correct
5 Correct 7 ms 29276 KB Output is correct
6 Correct 8 ms 29788 KB Output is correct
7 Correct 6 ms 29276 KB Output is correct
8 Correct 7 ms 29512 KB Output is correct
9 Correct 8 ms 31580 KB Output is correct
10 Incorrect 8 ms 29532 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #5
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 29276 KB Output is correct
2 Correct 8 ms 29532 KB Output is correct
3 Correct 7 ms 29456 KB Output is correct
4 Correct 7 ms 29276 KB Output is correct
5 Correct 7 ms 29276 KB Output is correct
6 Correct 8 ms 29788 KB Output is correct
7 Correct 6 ms 29276 KB Output is correct
8 Correct 7 ms 29512 KB Output is correct
9 Correct 8 ms 31580 KB Output is correct
10 Incorrect 8 ms 29532 KB Output isn't correct
11 Halted 0 ms 0 KB -