oj.uz

Submission #255696

# Submission time Handle Problem Language Result Execution time Memory
255696 2020-08-01T15:29:43 Z Akashi Parachute rings (IOI12_rings) C++14
38 / 100
 4000 ms 143608 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 tt[DIM], sz[DIM];
vector <int> cand;
vector <int> adj[DIM];
deque <int> lant[DIM];

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

    for (int i = 0; i < n ; ++i) {
        tt[i] = i, sz[i] = 1;
        lant[i].push_back(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 == lant[rA].back() || A == lant[rA].front()) && (B == lant[rB].back() || B == lant[rB].front())) {
            ///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 == lant[rA].back() && B == lant[rB].front()) {
                for (auto it : lant[rB]) lant[rA].push_back(it);
            } else if (A == lant[rA].back() && B == lant[rB].back()) {
                while (!lant[rB].empty()) {
                    lant[rA].push_back(lant[rB].back());
                    lant[rB].pop_back();
                }
            } else if (B == lant[rB].front()) {
                for (auto it : lant[rB]) lant[rA].push_front(it);
            } else {
                while (!lant[rB].empty()) {
                    lant[rA].push_front(lant[rB].back());
                    lant[rB].pop_back();
                }
            }

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

int CountCritical() {
    return ans;
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 70008 KB Output is correct
2 Correct 53 ms 70648 KB Output is correct
3 Correct 54 ms 70792 KB Output is correct
4 Correct 60 ms 70144 KB Output is correct
5 Correct 49 ms 70392 KB Output is correct
6 Correct 62 ms 70648 KB Output is correct
7 Correct 48 ms 70136 KB Output is correct
8 Correct 49 ms 70264 KB Output is correct
9 Correct 55 ms 70784 KB Output is correct
10 Correct 51 ms 70776 KB Output is correct

Subtask #2
0 / 17.0

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

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 70008 KB Output is correct
2 Correct 53 ms 70648 KB Output is correct
3 Correct 54 ms 70792 KB Output is correct
4 Correct 60 ms 70144 KB Output is correct
5 Correct 49 ms 70392 KB Output is correct
6 Correct 62 ms 70648 KB Output is correct
7 Correct 48 ms 70136 KB Output is correct
8 Correct 49 ms 70264 KB Output is correct
9 Correct 55 ms 70784 KB Output is correct
10 Correct 51 ms 70776 KB Output is correct
11 Correct 49 ms 70392 KB Output is correct
12 Correct 53 ms 70648 KB Output is correct
13 Correct 52 ms 70648 KB Output is correct
14 Correct 343 ms 70716 KB Output is correct
15 Correct 379 ms 70908 KB Output is correct
16 Correct 52 ms 70648 KB Output is correct
17 Correct 50 ms 70472 KB Output is correct
18 Correct 50 ms 70520 KB Output is correct
19 Correct 55 ms 71160 KB Output is correct
20 Correct 55 ms 71288 KB Output is correct

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 70008 KB Output is correct
2 Correct 53 ms 70648 KB Output is correct
3 Correct 54 ms 70792 KB Output is correct
4 Correct 60 ms 70144 KB Output is correct
5 Correct 49 ms 70392 KB Output is correct
6 Correct 62 ms 70648 KB Output is correct
7 Correct 48 ms 70136 KB Output is correct
8 Correct 49 ms 70264 KB Output is correct
9 Correct 55 ms 70784 KB Output is correct
10 Correct 51 ms 70776 KB Output is correct
11 Correct 49 ms 70392 KB Output is correct
12 Correct 53 ms 70648 KB Output is correct
13 Correct 52 ms 70648 KB Output is correct
14 Correct 343 ms 70716 KB Output is correct
15 Correct 379 ms 70908 KB Output is correct
16 Correct 52 ms 70648 KB Output is correct
17 Correct 50 ms 70472 KB Output is correct
18 Correct 50 ms 70520 KB Output is correct
19 Correct 55 ms 71160 KB Output is correct
20 Correct 55 ms 71288 KB Output is correct
21 Correct 73 ms 72184 KB Output is correct
22 Correct 92 ms 73464 KB Output is correct
23 Correct 118 ms 74488 KB Output is correct
24 Execution timed out 4054 ms 75228 KB Time limit exceeded
25 Halted 0 ms 0 KB -

Subtask #5
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 70008 KB Output is correct
2 Correct 53 ms 70648 KB Output is correct
3 Correct 54 ms 70792 KB Output is correct
4 Correct 60 ms 70144 KB Output is correct
5 Correct 49 ms 70392 KB Output is correct
6 Correct 62 ms 70648 KB Output is correct
7 Correct 48 ms 70136 KB Output is correct
8 Correct 49 ms 70264 KB Output is correct
9 Correct 55 ms 70784 KB Output is correct
10 Correct 51 ms 70776 KB Output is correct
11 Runtime error 118 ms 143608 KB Execution killed with signal 11 (could be triggered by violating memory limits)
12 Halted 0 ms 0 KB -