Submission #483382

#	Time	Username	Problem	Language	Result	Execution time	Memory
483382		syl123456	Parachute rings (IOI12_rings)	C++17	0 / 100	199 ms	262148 KiB

rings

#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<vector<int>> deg, pa, g;
vector<bool> fail;
vector<int> v, sz;
map<int, int> id;
int n, ans;

int extend() {
    deg.emplace_back(n, 0);
    pa.emplace_back(n);
    iota(all(pa.back()), 0);
    fail.push_back(false);
    return deg.size() - 1;
}

int find(int _id, int i) {
    return pa[_id][i] = pa[_id][i] == i ? i : find(_id, pa[_id][i]);
}

void upd(vector<int> tmp) {
    if (fail[0])
        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[0] = true;
}

void add(int _id, pi _e) {
    if (fail[_id])
        return;
    int x = _e.first, y = _e.second;
    if (++deg[_id][x] >= 3) {
        fail[_id] = true;
        return;
    }
    if (++deg[_id][y] >= 3) {
        fail[_id] = true;
        return;
    }
    x = find(_id, x), y = find(_id, y);
    if (x == y) {
        fail[_id] = true;
        return;
    }
    pa[_id][x] = y;
}

struct seg {
    int l, r;
    vector<pi> g;
    seg *ch[2]{};
    seg(int _l, int _r) : l(_l), r(_r) {
        if (l < r - 1)
            ch[0] = new seg(l, l + r >> 1), ch[1] = new seg(l + r >> 1, r);
    }
    void modify(int _l, int _r, pi _e) {
        if (_l >= _r)
            return;
        if (_l <= l && r <= _r) {
            g.push_back(_e);
            return;
        }
        push();
        if (_l < l + r >> 1)
            ch[0]->modify(_l, _r, _e);
        if (l + r >> 1 < _r)
            ch[1]->modify(_l, _r, _e);
    }
    void push() {
        if (!g.empty()) {
            ch[0]->g.insert(ch[0]->g.end(), all(g));
            ch[1]->g.insert(ch[1]->g.end(), all(g));
            g.clear();
        }
    }
    void build(int i) {
        if (l == r - 1) {
            if (!id.count(i))
                id[i] = extend();
            while (!g.empty())
                add(id[i], g.back()), g.pop_back();
            return;
        }
        push();
        ch[i >= l + r >> 1]->build(i);
    }
} *rt;

void Init(int N) {
    ans = n = N;
    extend();
    g.resize(n);
    sz.assign(n, 1);
    rt = new seg(0, n);
}

void Link(int x, int y) {
    if (fail[0])
        return;
    ++deg[0][x], ++deg[0][y];
    g[x].push_back(y), g[y].push_back(x);
    if (x > y)
        swap(x, y);
    rt->modify(0, x, pi(x, y));
    rt->modify(x + 1, y, pi(x, y));
    rt->modify(y + 1, n, pi(x, y));
    if (deg[0][x] == 4) {
        vector<int> tmp(1, x);
        upd(tmp);
    }
    else if (deg[0][x] == 3) {
        vector<int> tmp = g[x];
        tmp.push_back(x);
        upd(tmp);
    }
    if (deg[0][y] == 4) {
        vector<int> tmp(1, y);
        upd(tmp);
    }
    else if (deg[0][y] == 3) {
        vector<int> tmp = g[y];
        tmp.push_back(y);
        upd(tmp);
    }
    x = find(0, x), y = find(0, y);
    if (x == y) {
        if (!fail[0] && v.empty()) {
            if (ans == n)
                ans = sz[x];
            else
                ans = 0;
        }
    }
    else
        pa[0][x] = y, sz[y] += sz[x];
}

int CountCritical() {
    if (fail[0])
        return 0;
    if (v.empty())
        return ans;
    vector<int> tmp;
    for (int i : v) {
        rt->build(i);
        if (!fail[id[i]])
            tmp.push_back(i);
    }
    upd(tmp);
    return v.size();
}

Compilation message (stderr)

rings.cpp: In constructor 'seg::seg(int, int)':
rings.cpp:104:34: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  104 |             ch[0] = new seg(l, l + r >> 1), ch[1] = new seg(l + r >> 1, r);
      |                                ~~^~~
rings.cpp:104:63: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  104 |             ch[0] = new seg(l, l + r >> 1), ch[1] = new seg(l + r >> 1, r);
      |                                                             ~~^~~
rings.cpp: In member function 'void seg::modify(int, int, pi)':
rings.cpp:114:20: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  114 |         if (_l < l + r >> 1)
      |                  ~~^~~
rings.cpp:116:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  116 |         if (l + r >> 1 < _r)
      |             ~~^~~
rings.cpp: In member function 'void seg::build(int)':
rings.cpp:135:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  135 |         ch[i >= l + r >> 1]->build(i);
      |                 ~~^~~

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