oj.uz

Submission #255711

# Submission time Handle Problem Language Result Execution time Memory
255711 2020-08-01T16:02:35 Z Akashi Parachute rings (IOI12_rings) C++14
55 / 100
 4000 ms 76152 KB 
//#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.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 23808 KB Output is correct
2 Correct 17 ms 25132 KB Output is correct
3 Correct 18 ms 25216 KB Output is correct
4 Correct 15 ms 23936 KB Output is correct
5 Correct 16 ms 24192 KB Output is correct
6 Correct 17 ms 24192 KB Output is correct
7 Correct 16 ms 23900 KB Output is correct
8 Correct 17 ms 24064 KB Output is correct
9 Correct 18 ms 25216 KB Output is correct
10 Correct 17 ms 25088 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 533 ms 50512 KB Output is correct
2 Correct 1018 ms 66084 KB Output is correct
3 Correct 335 ms 43896 KB Output is correct
4 Correct 1308 ms 74780 KB Output is correct
5 Correct 1294 ms 74736 KB Output is correct
6 Correct 1264 ms 73592 KB Output is correct
7 Correct 328 ms 44152 KB Output is correct
8 Correct 1262 ms 72760 KB Output is correct
9 Correct 1302 ms 76152 KB Output is correct
10 Correct 903 ms 72952 KB Output is correct

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 23808 KB Output is correct
2 Correct 17 ms 25132 KB Output is correct
3 Correct 18 ms 25216 KB Output is correct
4 Correct 15 ms 23936 KB Output is correct
5 Correct 16 ms 24192 KB Output is correct
6 Correct 17 ms 24192 KB Output is correct
7 Correct 16 ms 23900 KB Output is correct
8 Correct 17 ms 24064 KB Output is correct
9 Correct 18 ms 25216 KB Output is correct
10 Correct 17 ms 25088 KB Output is correct
11 Correct 18 ms 25088 KB Output is correct
12 Correct 20 ms 25336 KB Output is correct
13 Correct 21 ms 25344 KB Output is correct
14 Correct 26 ms 25216 KB Output is correct
15 Correct 29 ms 25464 KB Output is correct
16 Correct 20 ms 24576 KB Output is correct
17 Correct 18 ms 24064 KB Output is correct
18 Correct 18 ms 24320 KB Output is correct
19 Correct 20 ms 24448 KB Output is correct
20 Correct 21 ms 25468 KB Output is correct

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 23808 KB Output is correct
2 Correct 17 ms 25132 KB Output is correct
3 Correct 18 ms 25216 KB Output is correct
4 Correct 15 ms 23936 KB Output is correct
5 Correct 16 ms 24192 KB Output is correct
6 Correct 17 ms 24192 KB Output is correct
7 Correct 16 ms 23900 KB Output is correct
8 Correct 17 ms 24064 KB Output is correct
9 Correct 18 ms 25216 KB Output is correct
10 Correct 17 ms 25088 KB Output is correct
11 Correct 18 ms 25088 KB Output is correct
12 Correct 20 ms 25336 KB Output is correct
13 Correct 21 ms 25344 KB Output is correct
14 Correct 26 ms 25216 KB Output is correct
15 Correct 29 ms 25464 KB Output is correct
16 Correct 20 ms 24576 KB Output is correct
17 Correct 18 ms 24064 KB Output is correct
18 Correct 18 ms 24320 KB Output is correct
19 Correct 20 ms 24448 KB Output is correct
20 Correct 21 ms 25468 KB Output is correct
21 Correct 34 ms 25848 KB Output is correct
22 Correct 50 ms 27000 KB Output is correct
23 Correct 58 ms 27900 KB Output is correct
24 Execution timed out 4073 ms 28360 KB Time limit exceeded
25 Halted 0 ms 0 KB -

Subtask #5
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 23808 KB Output is correct
2 Correct 17 ms 25132 KB Output is correct
3 Correct 18 ms 25216 KB Output is correct
4 Correct 15 ms 23936 KB Output is correct
5 Correct 16 ms 24192 KB Output is correct
6 Correct 17 ms 24192 KB Output is correct
7 Correct 16 ms 23900 KB Output is correct
8 Correct 17 ms 24064 KB Output is correct
9 Correct 18 ms 25216 KB Output is correct
10 Correct 17 ms 25088 KB Output is correct
11 Correct 533 ms 50512 KB Output is correct
12 Correct 1018 ms 66084 KB Output is correct
13 Correct 335 ms 43896 KB Output is correct
14 Correct 1308 ms 74780 KB Output is correct
15 Correct 1294 ms 74736 KB Output is correct
16 Correct 1264 ms 73592 KB Output is correct
17 Correct 328 ms 44152 KB Output is correct
18 Correct 1262 ms 72760 KB Output is correct
19 Correct 1302 ms 76152 KB Output is correct
20 Correct 903 ms 72952 KB Output is correct
21 Correct 18 ms 25088 KB Output is correct
22 Correct 20 ms 25336 KB Output is correct
23 Correct 21 ms 25344 KB Output is correct
24 Correct 26 ms 25216 KB Output is correct
25 Correct 29 ms 25464 KB Output is correct
26 Correct 20 ms 24576 KB Output is correct
27 Correct 18 ms 24064 KB Output is correct
28 Correct 18 ms 24320 KB Output is correct
29 Correct 20 ms 24448 KB Output is correct
30 Correct 21 ms 25468 KB Output is correct
31 Correct 34 ms 25848 KB Output is correct
32 Correct 50 ms 27000 KB Output is correct
33 Correct 58 ms 27900 KB Output is correct
34 Execution timed out 4073 ms 28360 KB Time limit exceeded
35 Halted 0 ms 0 KB -