Submission #741792

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
741792	2023-05-14T23:17:21 Z	Joshua_Andersson	Parachute rings (IOI12_rings)	C++17	100 / 100	1797 ms	148080 KB

rings

#undef _GLIBCXX_DEBUG                // disable run-time bound checking, etc
#pragma GCC optimize("Ofast,inline") // Ofast = O3,fast-math,allow-store-data-races,no-protect-parens
#pragma GCC optimize ("unroll-loops")

#pragma GCC target("bmi,bmi2,lzcnt,popcnt")                      // bit manipulation
#pragma GCC target("movbe")                                      // byte swap
#pragma GCC target("aes,pclmul,rdrnd")                           // encryption
#pragma GCC target("avx,avx2,f16c,fma,sse3,ssse3,sse4.1,sse4.2") // SIMD

#include <bits/stdc++.h>
#include <bits/extc++.h>
using namespace std;

#define enablell 0

typedef long long ll;
typedef unsigned long long ull;
#if enablell
#define int ll
#define inf int(1e18)
#define float double
#else
const int inf = int(2e9);
#endif
typedef vector<ull> vull;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<vvi> vvvi;
typedef vector<vvvi> vvvvi;
typedef vector<bool> vb;
typedef vector<vb> vvb;
typedef vector<vvb> vvvb;
typedef pair<int, int> p2;
typedef vector<p2> vp2;
typedef vector<vp2> vvp2;
typedef vector<vvp2> vvvp2;
typedef tuple<int, int, int> p3;
typedef vector<p3> vp3;
typedef vector<vp3> vvp3;
typedef vector<vvp3> vvvp3;
typedef tuple<int, int, int, int> p4;
typedef vector<p4> vp4;

#define PBDS 0
#define _LOCAL _MSC_VER > 0
#if _LOCAL
#define gc() getchar()
#define popcount(x) __popcnt(x)
#define leading_zeros(x) _lzcnt_u32(x)
uint32_t clz(uint32_t x) { return _lzcnt_u32(x); }
uint32_t ctz(uint32_t x) { return _tzcnt_u32(x); }
#define bswap64(x) _byteswap_uint64(x)
#define assert(x) debassert(x)
#else
#define popcount(x) __builtin_popcount(x)
uint32_t clz(uint32_t x) { return __builtin_clz(x); }
uint32_t ctz(uint32_t x) { return __builtin_ctzll(x); }
#define bswap64(x) __builtin_bswap64(x)
#define gc() getchar_unlocked()
#if PBDS
using namespace __gnu_pbds;
// lower_bound is now upper_bound and vice versa (multiset). generally a bit broken
template<typename T> using indexed_multiset = tree<int, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>;
template<typename T> using indexed_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
struct chash { // large odd number for C
    const uint64_t C = ll(4e18 * acos(0)) | 71;
    ll operator()(ll x) const { return __builtin_bswap64(x * C); }
};

template<typename T, typename U> using fast_map = __gnu_pbds::gp_hash_table<T, U, chash>;
template<typename T> using fast_set = __gnu_pbds::gp_hash_table<T, null_type, chash>;
template<typename T, typename H> using fast_set_h = __gnu_pbds::gp_hash_table<T, null_type, H>;
#endif

#endif

#define FAST_INPUT 0
#define FILE_TC 0
#if FILE_TC && _LOCAL
//ifstream filein("E:\\desktop\\code\\repos\\Comp prog\\x64\\Debug\\in.txt");
ifstream filein("C:\\users\\matis\\source\\repos\\comp_prog\\x64\\Release\\in.txt");
//ifstream filein("E:\\downloads\\test_data\\test_data\\005-case05.in");
//ifstream filein("E:\\desktop\\po-repos\\swedish-olympiad-2023\\online\\tomtplanering\\data\\secret\\group10\\010-case10.in");

#define cin filein
void fast() {}
#else
inline void fast() { ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); }
#endif

#if FAST_INPUT && (!FILE_TC || !_LOCAL)
inline void read(int& v) { v = 0; int sign = 1; char c = gc(); if (c == '-') { sign = -1; } else { v += c - '0'; } while ((c = gc()) && c != ' ' && c != '\n') { if (c == EOF) { v = -1; return; } v *= 10; v += c - '0'; } v *= sign; }
inline void read(int& u, int& v) { read(u); read(v); }
inline void read(int& u, int& v, int& k) { read(u); read(v); read(k); }
//inline void read(int& v) { char c; while ((c = getchar()) != EOF && c != ' ' && c != '\n') { v *= 10; v += c - '0'; } }
inline void read(string& s) { char c; while ((c = gc()) != EOF && c != '\n' && c != ' ') { s.push_back(c); } }
inline void readline(string& s) { char c; while ((c = gc()) != EOF && c != '\n') { s.push_back(c); } }
#else
template <typename T> inline void read(T& a) { cin >> a; }
template <typename T> inline void read(T& a, T& b) { cin >> a >> b; }
template <typename T> inline void read(T& a, T& b, T& c) { cin >> a >> b >> c; }
#endif
#define quit cout << endl; _Exit(0);
#define dread(type, a) type a; read(a)
#define dread2(type, a, b) dread(type, a); dread(type, b)
#define dread3(type, a, b, c) dread2(type, a, b); dread(type, c)
#define dread4(type, a, b, c, d) dread3(type, a, b, c); dread(type, d)
#define dread5(type, a, b, c, d, e) dread4(type, a, b, c, d); dread(type, e)
#define readvector(type, name, size) vector<type> name(size); rep(i,size) {dread(type,temp); name[i]=temp;}
#ifdef _DEBUG
#define noop cout << "";
#define deb __debugbreak();
#define debassert(expr) if(!(expr)) deb;
#define debif(expr) if(expr) deb;
#else
#define noop ;
#define deb ;
#define debif(expr) ;
#define debassert(expr) ;
#endif

#define rep(i, high) for (int i = 0; i < high; i++)
#define repp(i, low, high) for (int i = low; i < high; i++)
#define repe(i, container) for (auto& i : container)
#define per(i, high) for (int i = high-1; i >= 0; i--)
#define perr(i, low, high) for (int i = high-1; i >= low; i--)

#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
#define setcontains(set, x) (set.find(x) != set.end())
#define within(a, b, c, d) (a >= 0 && a < b && c >= 0 && c < d)
#define sz(container) ((int)container.size())
#define mp(a,b) (make_pair(a,b))

#define ceildiv(x,y) ((x + y - 1) / y)

template <typename T, typename U> inline void operator+=(pair<T, U>& l, const pair<T, U>& r) { l = { l.first + r.first,l.second + r.second }; }
template <typename T, typename U> inline pair<T, U> operator+(const pair<T, U> l, const pair<T, U> r) { return { l.first + r.first, l.second + r.second }; }
template <typename T, typename U> inline pair<T, U> operator-(const pair<T, U> l, const pair<T, U> r) { return { l.first - r.first, l.second - r.second }; }
template <typename T, typename U> inline pair<T, U> operator*(const pair<T, U> l, const int m) { return { l.first * m, l.second * m }; }
template <typename Out> inline void split(const string& s, char delim, Out result) { istringstream iss(s); string item; while (getline(iss, item, delim)) { *result++ = item; } }
inline vector<string> split(const string& s, char delim) { vector<string> elems; split(s, delim, back_inserter(elems)); return elems; }
vector<string> split(string s, string d) { size_t k = 0, n, e = d.length(); string t; vector<string> r; while ((n = s.find(d, k)) != string::npos) { t = s.substr(k, n - k); k = n + e; r.push_back(t); } r.push_back(s.substr(k)); return r; }
ll binpow(ll a, ll b) { ll res = 1; while (b > 0) { if (b & 1) res = res * a; a = a * a; b >>= 1; } return res; }
ll binpow(ll a, ll b, ll m) { a %= m; long long res = 1; while (b > 0) { if (b & 1) res = res * a % m; a = a * a % m; b >>= 1; } return res; } // For a < 2^31

#if 1
auto Start = chrono::high_resolution_clock::now();
void resettimer() { Start = chrono::high_resolution_clock::now(); }
int elapsedmillis() { return chrono::duration_cast<chrono::milliseconds>(chrono::high_resolution_clock::now() - Start).count(); }
random_device rd;
mt19937 rng(rd());
template<typename T, typename U> inline int randint(T lo, U hi) { return uniform_int_distribution<int>((int)lo, (int)hi)(rng); } // [lo,hi]
template<typename T> inline T randel(vector<T>& v) { return v[uniform_int_distribution<int>(int(0), int(v.size()) - int(1))(rng)]; } // [lo,hi]
#endif
const ll mod = 1e9 + 7;
vp2 dirs = { {0,1},{0,-1},{1,0},{-1,0}, {0,0} };

int state = 0;
int numcycles = 0;
int cyclelen = -1;
int n;
vp2 edgelist;
vvi edges;


int findlen(int u, int p, int start)
{
    if (u == start && u != p) return 0;
    repe(e, edges[u])
    {
        if (e != p)
        {
            int k = findlen(e, u, start);
            if (k != -1) return k + 1;
        }
    }
    return -1;
}

struct UF
{
    int n;
    vi par;
    vi size;
    vi deg;
    bool hascycle;

    UF(int n) : n(n), par(n), size(n, 1), deg(n)
    {
        rep(i, n) par[i] = i;
    }

    int find(int x) { return x == par[x] ? x : par[x] = find(par[x]); }

    int merge(int a, int b)
    {
        deg[a]++;
        deg[b]++;
        if (deg[a] > 2 || deg[b] > 2)
        {
            state = 2;
            return 1;
        }

        if (find(a)==find(b))
        {
            if (numcycles==0)
            {
                numcycles++;
                cyclelen = findlen(a,a,a);
                hascycle = 1;
                state = 1;
            }
            else
            {
                state = 3;
            }
        }
        else
        {
            a = find(a);
            b = find(b);
            if (size[a] < size[b]) swap(a, b);
            par[b] = a;
            size[a] += size[b];
        }
        return 0;
    }
};

struct UF2
{
    int n;
    vi par;
    vi size;
    vi deg;
    bool isgood=1;
    int excluded = -1;

    UF2(int n) : n(n), par(n), size(n, 1), deg(n)
    {
        rep(i, n) par[i] = i;
    }

    int find(int x) { return x == par[x] ? x : par[x] = find(par[x]); }

    void merge(int a, int b)
    {
        if (a == excluded || b == excluded) return;
        deg[a]++;
        deg[b]++;

        if (deg[a] > 2 || deg[b] > 2) isgood = 0;
        if (find(a)==find(b))
        {
            isgood = 0;
        }
        else
        {
            a = find(a);
            b = find(b);
            if (size[a] < size[b]) swap(a, b);
            par[b] = a;
            size[a] += size[b];
        }
    }
};

UF uf = UF(0);
vector<UF2> nodes;
void Init(int s)
{
    n = s;
    uf = UF(n);
    
    rep(i, 4) nodes.push_back(UF2(n));
    edges.resize(n);
}

void Link(int a, int b)
{
    edgelist.emplace_back(a, b);
    edges[a].emplace_back(b);
    edges[b].emplace_back(a);
    if (state<2)
    {
        if (uf.merge(a,b))
        {
            int d3 = -1;
            rep(i, n) if (uf.deg[i] == 3) d3 = i;

            nodes[0].excluded = d3;
            rep(i, 3)
            {
                nodes[i + 1].excluded = edges[d3][i];
            }

            repe(e, edgelist)
            {
                rep(i, 4)
                {
                    nodes[i].merge(e.first, e.second);
                }
            }

            rep(i, nodes.size())
            {
                if (!nodes[i].isgood)
                {
                    nodes.erase(begin(nodes) + i);
                    i--;
                }
            }
        }
    }
    else
    {
        rep(i, nodes.size())
        {
            nodes[i].merge(a, b);
            if (!nodes[i].isgood)
            {
                nodes.erase(begin(nodes) + i);
                i--;
            }
        }
    }
}

int CountCritical()
{
    if (state==0)
    {
        return n;
    }
    else if (state==1)
    {
        return cyclelen;
    }
    else if (state==2)
    {
        return nodes.size();
    }
    return 0;
}

Compilation message

rings.cpp: In function 'void Link(int, int)':
rings.cpp:122:40: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<UF2>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  122 | #define rep(i, high) for (int i = 0; i < high; i++)
......
  307 |             rep(i, nodes.size())
      |                 ~~~~~~~~~~~~~~~         
rings.cpp:307:13: note: in expansion of macro 'rep'
  307 |             rep(i, nodes.size())
      |             ^~~
rings.cpp:122:40: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<UF2>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  122 | #define rep(i, high) for (int i = 0; i < high; i++)
......
  319 |         rep(i, nodes.size())
      |             ~~~~~~~~~~~~~~~             
rings.cpp:319:9: note: in expansion of macro 'rep'
  319 |         rep(i, nodes.size())
      |         ^~~

Subtask #1

20.0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	2 ms	724 KB	Output is correct
3	Correct	3 ms	852 KB	Output is correct
4	Correct	1 ms	340 KB	Output is correct
5	Correct	2 ms	724 KB	Output is correct
6	Correct	2 ms	980 KB	Output is correct
7	Correct	1 ms	724 KB	Output is correct
8	Correct	2 ms	724 KB	Output is correct
9	Correct	3 ms	936 KB	Output is correct
10	Correct	3 ms	980 KB	Output is correct

Subtask #2

17.0 / 17.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	358 ms	63432 KB	Output is correct
2	Correct	957 ms	83988 KB	Output is correct
3	Correct	679 ms	83360 KB	Output is correct
4	Correct	1066 ms	134952 KB	Output is correct
5	Correct	1043 ms	135720 KB	Output is correct
6	Correct	1103 ms	148080 KB	Output is correct
7	Correct	687 ms	83660 KB	Output is correct
8	Correct	1659 ms	119892 KB	Output is correct
9	Correct	1797 ms	133508 KB	Output is correct
10	Correct	675 ms	132120 KB	Output is correct

Subtask #3

18.0 / 18.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	2 ms	724 KB	Output is correct
3	Correct	3 ms	852 KB	Output is correct
4	Correct	1 ms	340 KB	Output is correct
5	Correct	2 ms	724 KB	Output is correct
6	Correct	2 ms	980 KB	Output is correct
7	Correct	1 ms	724 KB	Output is correct
8	Correct	2 ms	724 KB	Output is correct
9	Correct	3 ms	936 KB	Output is correct
10	Correct	3 ms	980 KB	Output is correct
11	Correct	3 ms	852 KB	Output is correct
12	Correct	5 ms	1620 KB	Output is correct
13	Correct	5 ms	1620 KB	Output is correct
14	Correct	4 ms	1144 KB	Output is correct
15	Correct	3 ms	2004 KB	Output is correct
16	Correct	4 ms	1696 KB	Output is correct
17	Correct	4 ms	1364 KB	Output is correct
18	Correct	5 ms	2132 KB	Output is correct
19	Correct	6 ms	1748 KB	Output is correct
20	Correct	6 ms	1620 KB	Output is correct

Subtask #4

14.0 / 14.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	2 ms	724 KB	Output is correct
3	Correct	3 ms	852 KB	Output is correct
4	Correct	1 ms	340 KB	Output is correct
5	Correct	2 ms	724 KB	Output is correct
6	Correct	2 ms	980 KB	Output is correct
7	Correct	1 ms	724 KB	Output is correct
8	Correct	2 ms	724 KB	Output is correct
9	Correct	3 ms	936 KB	Output is correct
10	Correct	3 ms	980 KB	Output is correct
11	Correct	3 ms	852 KB	Output is correct
12	Correct	5 ms	1620 KB	Output is correct
13	Correct	5 ms	1620 KB	Output is correct
14	Correct	4 ms	1144 KB	Output is correct
15	Correct	3 ms	2004 KB	Output is correct
16	Correct	4 ms	1696 KB	Output is correct
17	Correct	4 ms	1364 KB	Output is correct
18	Correct	5 ms	2132 KB	Output is correct
19	Correct	6 ms	1748 KB	Output is correct
20	Correct	6 ms	1620 KB	Output is correct
21	Correct	18 ms	5968 KB	Output is correct
22	Correct	30 ms	9416 KB	Output is correct
23	Correct	35 ms	11708 KB	Output is correct
24	Correct	36 ms	8276 KB	Output is correct
25	Correct	18 ms	8660 KB	Output is correct
26	Correct	44 ms	8404 KB	Output is correct
27	Correct	43 ms	11572 KB	Output is correct
28	Correct	33 ms	8020 KB	Output is correct
29	Correct	30 ms	9044 KB	Output is correct
30	Correct	53 ms	13900 KB	Output is correct

Subtask #5

31.0 / 31.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	2 ms	724 KB	Output is correct
3	Correct	3 ms	852 KB	Output is correct
4	Correct	1 ms	340 KB	Output is correct
5	Correct	2 ms	724 KB	Output is correct
6	Correct	2 ms	980 KB	Output is correct
7	Correct	1 ms	724 KB	Output is correct
8	Correct	2 ms	724 KB	Output is correct
9	Correct	3 ms	936 KB	Output is correct
10	Correct	3 ms	980 KB	Output is correct
11	Correct	358 ms	63432 KB	Output is correct
12	Correct	957 ms	83988 KB	Output is correct
13	Correct	679 ms	83360 KB	Output is correct
14	Correct	1066 ms	134952 KB	Output is correct
15	Correct	1043 ms	135720 KB	Output is correct
16	Correct	1103 ms	148080 KB	Output is correct
17	Correct	687 ms	83660 KB	Output is correct
18	Correct	1659 ms	119892 KB	Output is correct
19	Correct	1797 ms	133508 KB	Output is correct
20	Correct	675 ms	132120 KB	Output is correct
21	Correct	3 ms	852 KB	Output is correct
22	Correct	5 ms	1620 KB	Output is correct
23	Correct	5 ms	1620 KB	Output is correct
24	Correct	4 ms	1144 KB	Output is correct
25	Correct	3 ms	2004 KB	Output is correct
26	Correct	4 ms	1696 KB	Output is correct
27	Correct	4 ms	1364 KB	Output is correct
28	Correct	5 ms	2132 KB	Output is correct
29	Correct	6 ms	1748 KB	Output is correct
30	Correct	6 ms	1620 KB	Output is correct
31	Correct	18 ms	5968 KB	Output is correct
32	Correct	30 ms	9416 KB	Output is correct
33	Correct	35 ms	11708 KB	Output is correct
34	Correct	36 ms	8276 KB	Output is correct
35	Correct	18 ms	8660 KB	Output is correct
36	Correct	44 ms	8404 KB	Output is correct
37	Correct	43 ms	11572 KB	Output is correct
38	Correct	33 ms	8020 KB	Output is correct
39	Correct	30 ms	9044 KB	Output is correct
40	Correct	53 ms	13900 KB	Output is correct
41	Correct	208 ms	55116 KB	Output is correct
42	Correct	716 ms	95464 KB	Output is correct
43	Correct	239 ms	76608 KB	Output is correct
44	Correct	505 ms	79972 KB	Output is correct
45	Correct	625 ms	90600 KB	Output is correct
46	Correct	632 ms	111772 KB	Output is correct
47	Correct	914 ms	122740 KB	Output is correct
48	Correct	372 ms	83932 KB	Output is correct
49	Correct	655 ms	124024 KB	Output is correct
50	Correct	679 ms	122384 KB	Output is correct
51	Correct	269 ms	65436 KB	Output is correct
52	Correct	419 ms	65048 KB	Output is correct
53	Correct	360 ms	83384 KB	Output is correct
54	Correct	1317 ms	104864 KB	Output is correct
55	Correct	931 ms	88508 KB	Output is correct