oj.uz

Submission #255708

# Submission time Handle Problem Language Result Execution time Memory
255708 2020-08-01T15:53:21 Z Akashi Parachute rings (IOI12_rings) C++14
0 / 100
 11 ms 9344 KB 
//#include "rings.h"
#include <bits/stdc++.h>
using namespace std;

const int DIM = 1e5 + 5;

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];
int 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;
}

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) {
        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();
    }

    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();
}

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] = Front[rB];
            else if (A == Back[rA] && B == Back[rB]) Back[rA] = Back[rB];
            else if (B == Front[rB]) Front[rA] = Front[rB];
            else Front[rA] = Back[rB];

        } else {
            ///cazul mai naspa in care unesc 2 lanturi
            f(A, B, rA, rB);
        }
    }
}

int CountCritical() {
    return ans;
}

Subtask #1
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2688 KB Output is correct
2 Incorrect 3 ms 2944 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Runtime error 11 ms 9344 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #3
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2688 KB Output is correct
2 Incorrect 3 ms 2944 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2688 KB Output is correct
2 Incorrect 3 ms 2944 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2688 KB Output is correct
2 Incorrect 3 ms 2944 KB Output isn't correct
3 Halted 0 ms 0 KB -