Submission #255711

#	Time	Username	Problem	Language	Result	Execution time	Memory
255711		Akashi	Parachute rings (IOI12_rings)	C++14	55 / 100	4073 ms	76152 KiB

rings

//#include "rings.h"
#include <bits/stdc++.h>
using namespace std;

const int DIM = 1e6;

int ans;
int tip; /// 0 daca nu am restrictii, 1 daca am un ciclu simplu, 2 daca deja am putini candidati
int which; ///ce lant e ciclu simplu
int r1, r2; ///lanturile pe care am nodurile critice
int n;
int gr[DIM], Front[DIM], Back[DIM];

int tt[DIM], sz[DIM];
vector <int> cand;
vector <int> adj[DIM];

void Init(int N_) {
    n = N_; ans = n; tip = 0;

    for (int i = 0; i < n ; ++i) {
        tt[i] = i, sz[i] = 1;
        Front[i] = Back[i] = i;
    }
}

int find(int nod) {
    if (nod != tt[nod]) return (tt[nod] = find(tt[nod]));
    return nod;
}

void get_cand(int A, vector <int> &cand) {
    if (gr[A] >= 4) cand.push_back(A);
    else if (gr[A] == 3) {
        cand.push_back(A);
        for (auto it : adj[A]) cand.push_back(it);
    }
}

void unite(vector <int> &cand, vector <int> candA, vector <int> candB) {
    cand.clear();

    if (candA.empty()) cand = candB;
    else if (candB.empty()) cand = candA;
    else {
        for (auto itA : candA)
            for (auto itB : candB)
                if (itA == itB) {cand.push_back(itA); break ;}
    }
}

bool viz[DIM], ign[DIM], mark[DIM];
bool check(int nod, int papa = -1) {
    viz[nod] = true;

    for (auto it : adj[nod]) {
        if (ign[it]) continue ;
        if (it == papa) continue ;
        if (viz[it]) return false;

        check(it, nod);
    }

    return true;
}

bool change;
void f(int A, int B, int rA, int rB) {
    mark[rA] = mark[rB] = 1;
    if (tip == 0) {
        tip = 2;
        vector <int> candB;

        get_cand(A, cand);
        get_cand(B, candB);
        unite(cand, cand, candB);
    }
    else if (tip == 2) {
        change = true;
        vector <int> candA, candB;

        get_cand(A, candA);
        get_cand(B, candB);

        unite(candA, candA, candB);
        unite(cand, cand, candA);
    }
    else if (tip == 1) {
        if (find(which) == rB) swap(A, B), swap(rA, rB);

        if (find(which) == rA) {
            tip = 2;
            vector <int> candB;

            get_cand(A, cand);
            get_cand(B, candB);
            unite(cand, cand, candB);

            vector <int> candA;
            for (auto it : cand)
                if (find(it) == rA) candA.push_back(it);

            cand.clear();
            cand = candA;

        } else cand.clear();
    }

    ans = cand.size();
}

void Link(int A, int B) {
    if (ans == 0) return ;

    ++gr[A]; ++gr[B];
    adj[A].push_back(B);
    adj[B].push_back(A);

    int rA = find(A), rB = find(B);

    if (rA == rB) {
        if (gr[A] == gr[B] && gr[A] == 2) {
            ///am creat un ciclu simplu
            if (tip == 0) {
                tip = 1;
                which = find(A);
                ans = sz[rA];
                mark[rA] = 1;
            } else if (tip == 1) {
                ans = 0;
                return ;
            } else {
                vector <int> candA;
                for (auto it : cand)
                    if (find(it) == rA) candA.push_back(it);

                cand.clear();
                cand = candA;
            }
        } else {
            ///am creat (cel putin) un nod de grad 3
            f(A, B, rA, rB);
        }

    } else {
        ///TODO : sa am grija cand unesc 2 lanturi pe care le-am 'legat' deja la mijloc
        if (!(mark[rA] || mark[rB]) && gr[A] <= 2 && gr[B] <= 2 && (A == Back[rA] || A == Front[rA]) && (B == Back[rB] || B == Front[rB])) {
            ///cazul lejer in care unesc 2 lanturi
            if (sz[rA] < sz[rB]) swap(A, B), swap(rA, rB);
            sz[rA] += sz[rB]; tt[rB] = rA;

            if (A == Back[rA] && B == Front[rB]) Back[rA] = Back[rB];
            else if (A == Back[rA] && B == Back[rB]) Back[rA] = Front[rB];
            else if (B == Front[rB]) Front[rA] = Back[rB];
            else Front[rA] = Front[rB];
        } else {
            ///cazul mai naspa in care unesc 2 lanturi
            f(A, B, rA, rB);
        }
    }
}

int CountCritical() {
    if (change) {
        vector <int> candA;
        for (auto it : cand) {
            ign[it] = 1;
            memset(viz, 0, sizeof(viz));
            bool ok = true;

            for (auto x : adj[it]) {
                if (viz[x]) continue ;
                ok = check(x);
                if (!ok) break ;
            }

            if (ok) candA.push_back(it);
            ign[it] = 0;
        }

        cand.clear();
        cand = candA;

        ans = cand.size();
    }

    change = false;
    return ans;
}

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