oj.uz

Submission #574409

# Submission time Handle Problem Language Result Execution time Memory
574409 2022-06-08T13:40:51 Z MohamedFaresNebili Parachute rings (IOI12_rings) C++14
20 / 100
 4000 ms 42364 KB 
#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];
        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);
        }
        int CountCritical() {
            int res = 0;
            for(int l = 0; l < N; l++) {
                if(rem[l]) continue;
                vis[l] = 2; bool ok = 1;
                for(int i = 0; i < N; i++) {
                    if(vis[i]) continue;
                    ok &= dfs(i, i);
                }
                res += ok; fill(vis, vis + N, 0);
                if(!ok) rem[l] = 1;
            }
            return res;
        }

Compilation message

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;
      |                        ~~~~~^~~

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 23764 KB Output is correct
2 Correct 392 ms 24012 KB Output is correct
3 Correct 574 ms 24020 KB Output is correct
4 Correct 30 ms 23772 KB Output is correct
5 Correct 213 ms 24000 KB Output is correct
6 Correct 637 ms 24260 KB Output is correct
7 Correct 181 ms 23852 KB Output is correct
8 Correct 321 ms 24048 KB Output is correct
9 Correct 579 ms 24128 KB Output is correct
10 Correct 589 ms 24204 KB Output is correct

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4011 ms 42364 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 23764 KB Output is correct
2 Correct 392 ms 24012 KB Output is correct
3 Correct 574 ms 24020 KB Output is correct
4 Correct 30 ms 23772 KB Output is correct
5 Correct 213 ms 24000 KB Output is correct
6 Correct 637 ms 24260 KB Output is correct
7 Correct 181 ms 23852 KB Output is correct
8 Correct 321 ms 24048 KB Output is correct
9 Correct 579 ms 24128 KB Output is correct
10 Correct 589 ms 24204 KB Output is correct
11 Execution timed out 4074 ms 24080 KB Time limit exceeded
12 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 23764 KB Output is correct
2 Correct 392 ms 24012 KB Output is correct
3 Correct 574 ms 24020 KB Output is correct
4 Correct 30 ms 23772 KB Output is correct
5 Correct 213 ms 24000 KB Output is correct
6 Correct 637 ms 24260 KB Output is correct
7 Correct 181 ms 23852 KB Output is correct
8 Correct 321 ms 24048 KB Output is correct
9 Correct 579 ms 24128 KB Output is correct
10 Correct 589 ms 24204 KB Output is correct
11 Execution timed out 4074 ms 24080 KB Time limit exceeded
12 Halted 0 ms 0 KB -

Subtask #5
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 23764 KB Output is correct
2 Correct 392 ms 24012 KB Output is correct
3 Correct 574 ms 24020 KB Output is correct
4 Correct 30 ms 23772 KB Output is correct
5 Correct 213 ms 24000 KB Output is correct
6 Correct 637 ms 24260 KB Output is correct
7 Correct 181 ms 23852 KB Output is correct
8 Correct 321 ms 24048 KB Output is correct
9 Correct 579 ms 24128 KB Output is correct
10 Correct 589 ms 24204 KB Output is correct
11 Execution timed out 4011 ms 42364 KB Time limit exceeded
12 Halted 0 ms 0 KB -