Submission #574328

#	Time	Username	Problem	Language	Result	Execution time	Memory
574328		FatihSolak	Parachute rings (IOI12_rings)	C++17	100 / 100	2749 ms	161492 KiB

rings

#include <bits/stdc++.h>
using namespace std;
#define N 1000005
struct DSU{
    vector<int> ch;
    vector<int> cnt;
    vector<int> sz;
    vector<int> par;
    vector<int> cycles;
    int n; 
    int maxi;
    DSU(int size){
        n = size;
        maxi = 0;
        cnt.assign(n,0);
        sz.assign(n,1);
        ch.assign(n,0);
        par.assign(n,0);
        for(int i = 0;i<n;i++){
            par[i] = i;
        }
    }
    int find(int a){
        if(a == par[a])return a;
        return par[a] = find(par[a]);
    }
    void add(int a,int b){
        ch[a]++;
        ch[b]++;
        maxi = max(maxi,ch[a]);
        maxi = max(maxi,ch[b]);
        a = find(a);
        b = find(b);
        if(a == b){
            cnt[b]++;
            if(cnt[b] >= sz[b]){
                cycles.push_back(sz[b]);
            }
            return;
        }
        par[a] = b;
        sz[b] += sz[a];
        cnt[b] += cnt[a] + 1;
        cnt[a] = sz[a] = 0;
        if(cnt[b] >= sz[b]){
            cycles.push_back(sz[b]);
        }
    }

};
int n;
vector<int> nodes;
vector<DSU> graphs;
vector<int> adj[N];
void Init(int N_) {
    n = N_;
    nodes.push_back(-1);
    DSU tmp(n);
    graphs.push_back(tmp);
}

void Link(int a, int b) {
    adj[a].push_back(b);
    adj[b].push_back(a);
    graphs[0].add(a,b);
    if(graphs[0].maxi >= 3 && graphs.size() == 1){
        for(int i = 0;i<n;i++){
            if(adj[i].size() == 3){
                nodes.push_back(i);
                for(auto u:adj[i]){
                    nodes.push_back(u);
                }
                break;
            }
        }
        for(int j = 1;j<nodes.size();j++){
            DSU tmp(n);
            graphs.push_back(tmp);
            for(int i = 0;i<n;i++){
                if(i == nodes[j])continue;
                for(auto u:adj[i]){
                    if(u == nodes[j] || i > u)continue;
                    //cout << nodes[j] << " " << i << "  " << u << endl;
                    graphs[j].add(i,u);
                }
            }
        }
    }
    else if(graphs[0].maxi >= 3){
        for(int j = 1;j<nodes.size();j++){
            if(a == nodes[j] || b == nodes[j])continue;
            graphs[j].add(a,b);
        }
    }
}

int CountCritical() {
    if(graphs[0].maxi < 3){
        int ans = n;
        if(graphs[0].cycles.size() > 1)ans = 0;
        if(graphs[0].cycles.size() == 1)ans = graphs[0].cycles[0];
        return ans;
    }
    int ans = 0;
    for(int i = 1;i<nodes.size();i++){
        ans += (graphs[i].maxi < 3 && graphs[i].cycles.size() == 0);
    }
    return ans;
}

Compilation message (stderr)

rings.cpp: In function 'void Link(int, int)':
rings.cpp:76:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   76 |         for(int j = 1;j<nodes.size();j++){
      |                       ~^~~~~~~~~~~~~
rings.cpp:90:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   90 |         for(int j = 1;j<nodes.size();j++){
      |                       ~^~~~~~~~~~~~~
rings.cpp: In function 'int CountCritical()':
rings.cpp:105:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  105 |     for(int i = 1;i<nodes.size();i++){
      |                   ~^~~~~~~~~~~~~

• Subtask 1: 20 / 20
• Subtask 2: 17 / 17
• Subtask 3: 18 / 18
• Subtask 4: 14 / 14
• Subtask 5: 31 / 31