Submission #574417

#	Time	Username	Problem	Language	Result	Execution time	Memory
574417		MohamedFaresNebili	Parachute rings (IOI12_rings)	C++14	0 / 100	784 ms	59372 KiB

rings

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>

        using namespace std;
        using namespace __gnu_pbds;

        using ll = long long;
        using ii = pair<ll, ll>;
        using vi = vector<int>;

        #define pb push_back
        #define pp pop_back
        #define ff first
        #define ss second
        #define lb lower_bound

        typedef tree<int, null_type, less<int>, rb_tree_tag,
            tree_order_statistics_node_update> indexed_set;

        const int oo = 1e18 + 7;

        int N; int vis[1000001];
        vector<int> adj[1000001], S;
        bool rem[100001];

        void Init(int n) { N = n; }
        void Link(int a, int b) {
            adj[a].pb(b), adj[b].pb(a);
        }
        bool dfs(int v, int p) {
            if(vis[v]) return 0;
            int children = 0; vis[v] = 1; bool ok = 1;
            for(auto u : adj[v]) {
                if(vis[u] == 2 || u == p) continue;
                children++; ok &= dfs(u, v);
            }
            if(v == p) return (ok && children <= 2);
            return (ok && children <= 1);
        }
        void dfs(int v) {
            S.pb(v); vis[v] = 1;
            for(auto u : adj[v]) {
                if(vis[u]) continue;
                dfs(u);
            }
        }
        int CountCritical() {
            int res = 0;
            int curr = 0; int node = 0;
            fill(vis, vis + N, 0);
            for(int l = 0; l < N; l++) {
                if(vis[l]) continue;
                bool ok = dfs(l, l);
                if(!ok) curr++, node = l;
            }

            if(curr > 1) return 0;
            if(curr == 0) return N;

            fill(vis, vis + N, 0);
            S.clear(); dfs(node);
            int arr[5]{0};

            for(auto v : S) {
                int k = adj[v].size();
                if(k > 2) continue;
                arr[k]++;
            }

            for(auto v : S) {
                int p = adj[v].size();
                if(p <= 2) arr[p]--;
                for(auto u : adj[v]) {
                    int k = adj[u].size();
                    if(k <= 2) arr[k]--;
                    k--;
                    if(k <= 2) arr[k]++;
                }
                if(arr[1] == 2 && arr[2] == S.size() - arr[0] - arr[1] - 1) res++;
                if(p <= 2) arr[p]++;
                for(auto u : adj[v]) {
                    int k = adj[u].size();
                    if(k <= 2) arr[k]++;
                    k--;
                    if(k <= 2) arr[k]--;
                }
            }
            return res;
        }

Compilation message (stderr)

rings.cpp:20:29: warning: overflow in conversion from 'double' to 'int' changes value from '1.0e+18' to '2147483647' [-Woverflow]
   20 |         const int oo = 1e18 + 7;
      |                        ~~~~~^~~
rings.cpp: In function 'int CountCritical()':
rings.cpp:79:42: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   79 |                 if(arr[1] == 2 && arr[2] == S.size() - arr[0] - arr[1] - 1) res++;
      |                                   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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