oj.uz

Submission #880175

# Submission time Handle Problem Language Result Execution time Memory
880175 2023-11-29T01:29:58 Z abcvuitunggio Parachute rings (IOI12_rings) C++17
0 / 100
 1566 ms 121448 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){
                deg2[a]++;
                deg2[v]++;
                if (deg2[a]>1){
                    focus(a);
                    focused=a;
                    return;
                }
                if (deg2[v]>1){
                    focus(v);
                    focused=v;
                    return;
                }
            }
    }
    if (deg[b]==3){
        cnt2++;
        for (int v:ke[b])
            if (deg[v]>2){
                deg2[b]++;
                deg2[v]++;
                if (deg2[b]>1){
                    focus(a);
                    focused=a;
                    return;
                }
                if (deg2[v]>1){
                    focus(v);
                    focused=v;
                    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);
        }
    }
    cnt=cnt2;
}
int CountCritical(){
    if (focused!=-1)
        return ch[0];
    if (cnt>2)
        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:111:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  111 |             for (int i=0;i<candidates.size();i++)
      |                          ~^~~~~~~~~~~~~~~~~~
rings.cpp:115:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  115 |             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:140:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  140 |             for (int i=0;i<candidates.size();i++)
      |                          ~^~~~~~~~~~~~~~~~~~
rings.cpp: In function 'int CountCritical()':
rings.cpp:154:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  154 |         for (int i=0;i<candidates.size();i++)
      |                      ~^~~~~~~~~~~~~~~~~~

Subtask #1
0 / 20.0

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

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 311 ms 72116 KB Output is correct
2 Correct 610 ms 87012 KB Output is correct
3 Correct 405 ms 79672 KB Output is correct
4 Correct 930 ms 107692 KB Output is correct
5 Correct 912 ms 121448 KB Output is correct
6 Correct 921 ms 120328 KB Output is correct
7 Correct 397 ms 89312 KB Output is correct
8 Correct 1226 ms 117732 KB Output is correct
9 Incorrect 1566 ms 121240 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #3
0 / 18.0

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

Subtask #4
0 / 14.0

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

Subtask #5
0 / 31.0

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