oj.uz

Submission #483224

# Submission time Handle Problem Language Result Execution time Memory
483224 2021-10-28T09:37:29 Z syl123456 Parachute rings (IOI12_rings) C++17
0 / 100
 1039 ms 109368 KB 
#include <bits/stdc++.h>
#define all(i) (i).begin(), (i).end()
using namespace std;
template<typename T1, typename T2>
ostream& operator << (ostream &i, pair<T1, T2> j) {
    return i << j.first << ' ' << j.second;
}
template<typename T>
ostream& operator << (ostream &i, vector<T> j) {
    i << '{' << j.size() << ':';
    for (T ii : j) i << ' ' << ii;
    return i << '}';
}
void Debug(bool _split) {}
template<typename T1, typename ...T2>
void Debug(bool _split, T1 x, T2 ...args) {
    if (_split)
        cerr << ", ";
    cerr << x, Debug(true, args...);
}
template<typename T>
void Debuga(T *i, int n) {
    cerr << '[';
    for (int j = 0; j < n; ++j) cerr << i[j] << " ]"[j == n - 1];
    cerr << endl;
}
#ifdef SYL
#define debug(args...) cerr << "Line(" << __LINE__ << ") -> [" << #args << "] is [", Debug(false, args), cerr << ']' << endl
#define debuga(i) cerr << "Line(" << __LINE__ << ") -> [" << #i << "] is ", Debuga(i, sizeof(i) / sizeof(typeid(*i).name()))
#else
#define debug(args...) void(0)
#define debuga(i) void(0)
#endif
typedef long long ll;
typedef pair<int, int> pi;
const int inf = 0x3f3f3f3f, lg = 20;
const ll mod = 1e9 + 7, INF = 0x3f3f3f3f3f3f3f3f;

vector<int> deg, rt, stk, ring;
vector<int> v;
vector<vector<int>> g;
vector<bool> vis;
bool fail, first;
int n;

int find(int i) {
    return rt[i] = rt[i] == i ? i : find(rt[i]);
}

void dfs(int i, int p) {
    vis[i] = true;
    stk.push_back(i);
    for (int j : g[i])
        if (j != p) {
            if (!vis[j])
                dfs(j, i);
            else {
                while (stk.back() != j)
                    ring.push_back(stk.back()), stk.pop_back();
                ring.push_back(j);
                return;
            }
            if (!ring.empty())
                return;
        }
    stk.pop_back();
}

void upd(vector<int> tmp) {
    if (fail)
        return;
    if (v.empty()) {
        v = tmp;
        return;
    }
    for (int i = 0; i < (int)v.size(); ) {
        bool find = false;
        for (int j : tmp)
            if (v[i] == j) {
                find = true;
            }
        if (!find)
            swap(v[i], v.back()), v.pop_back();
        else
            ++i;
    }
    if (v.empty())
        fail = true;
}

void Init(int N) {
    deg.assign(N, 0);
    rt.resize(N);
    iota(all(rt), 0);
    vis.assign(N, false);
    g.assign(N, vector<int>());
    fail = false, first = true;
    n = N;
}

void Link(int x, int y) {
    if (fail)
        return;
    ++deg[x], ++deg[y];
    g[x].push_back(y), g[y].push_back(x);
    if (deg[x] == 4) {
        vector<int> tmp(1, x);
        upd(tmp);
    }
    else if (deg[x] == 3) {
        vector<int> tmp = g[x];
        tmp.push_back(x);
        upd(tmp);
    }
    if (fail)
        return;
    if (deg[y] == 4) {
        vector<int> tmp(1, y);
        upd(tmp);
    }
    else if (deg[y] == 3) {
        vector<int> tmp = g[y];
        tmp.push_back(y);
        upd(tmp);
    }
    if (fail)
        return;
    if (find(x) == find(y)) {
        if (first) {
            first = false;
            dfs(x, -1);
            debug(ring);
            upd(ring);
        }
    }
    else {
        rt[find(x)] = find(y);
    }
}

int CountCritical() {
    if (fail)
        return 0;
    if (v.empty())
        return n;
    return v.size();
}

Subtask #1
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 2 ms 588 KB Output is correct
3 Correct 2 ms 588 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 2 ms 588 KB Output is correct
6 Correct 3 ms 980 KB Output is correct
7 Correct 1 ms 460 KB Output is correct
8 Incorrect 2 ms 588 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 317 ms 33076 KB Output is correct
2 Correct 698 ms 51232 KB Output is correct
3 Correct 180 ms 34016 KB Output is correct
4 Correct 905 ms 64832 KB Output is correct
5 Correct 1035 ms 66720 KB Output is correct
6 Correct 1039 ms 109368 KB Output is correct
7 Correct 173 ms 34176 KB Output is correct
8 Correct 835 ms 60856 KB Output is correct
9 Correct 945 ms 64700 KB Output is correct
10 Incorrect 582 ms 63516 KB Output isn't correct

Subtask #3
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 2 ms 588 KB Output is correct
3 Correct 2 ms 588 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 2 ms 588 KB Output is correct
6 Correct 3 ms 980 KB Output is correct
7 Correct 1 ms 460 KB Output is correct
8 Incorrect 2 ms 588 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 2 ms 588 KB Output is correct
3 Correct 2 ms 588 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 2 ms 588 KB Output is correct
6 Correct 3 ms 980 KB Output is correct
7 Correct 1 ms 460 KB Output is correct
8 Incorrect 2 ms 588 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #5
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 2 ms 588 KB Output is correct
3 Correct 2 ms 588 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 2 ms 588 KB Output is correct
6 Correct 3 ms 980 KB Output is correct
7 Correct 1 ms 460 KB Output is correct
8 Incorrect 2 ms 588 KB Output isn't correct
9 Halted 0 ms 0 KB -