oj.uz

Submission #350966

# Submission time Handle Problem Language Result Execution time Memory
350966 2021-01-19T10:37:37 Z talant117408 Parachute rings (IOI12_rings) C++17
37 / 100
 1278 ms 114400 KB 
#include <bits/stdc++.h>
#ifndef EVAL
#include "grader.cpp"
#endif

using namespace std;

typedef long long ll;
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;

#define precision(n) fixed << setprecision(n)
#define pb push_back
#define ub upper_bound
#define lb lower_bound
#define mp make_pair
#define eps (double)1e-9
#define PI 2*acos(0.0)
#define endl "\n"
#define sz(v) int((v).size())
#define all(v) v.begin(),v.end()
#define rall(v) v.rbegin(),v.rend()
#define do_not_disturb ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define OK cout << "OK" << endl;

vector <vector <int>> graph;
bool in_cycle[1000007];
int n, cycles, cnt, used[1000007], used2[1000007], spcycle;
vector <int> st, to_be;

void dfs(int v, int p = -1){
    st.pb(v);
    used[v] = 1;
    for(auto to : graph[v]){
        if(p == to) continue;
        if(used[to] == 1){
            int flag = 0;
            if(!cycles){
                for(auto to2 : st){
                    if(to2 == to) flag = 1;
                    if(flag) in_cycle[to2] = 1;
                }
            }
            cycles++;
        }
        else if(!used[to]){
            dfs(to, v);
        }
    }
    used[v] = 2;
    st.pop_back();
}

void dfs2(int v, int p = -1){
    used2[v] = 1;
    cnt++;
    if(in_cycle[v]) spcycle++;
    for(auto to : graph[v]){
        if(in_cycle[v] && !in_cycle[to]){
            to_be.pb(to);
        }
        if(p == to) continue;
        if(!used2[to]) dfs2(to, v);
    }
}

void Init(int N) {
    n = N;
    graph.resize(n+1);
}

void Link(int A, int B) {
    graph[A].pb(B);
    graph[B].pb(A);
}

int CountCritical(){
    int special[n];
    for(int i = 0; i < n; i++){
        used[i] = 0;
        special[i] = 0;
        used2[i] = 0;
        in_cycle[i] = 0;
    }
    int fing_cycles = 0, saiz = 0;
    for(int i = 0; i < n; i++){
        if(!used[i]){
            cycles = 0;
            cnt = 0;
            spcycle = 0;
            to_be.clear();
            st.clear();
            dfs(i);
            if(cycles == 1){
                dfs2(i);
                for(auto to : to_be) special[to] = 1;
                if(cnt == spcycle){
                    fing_cycles++;
                    saiz = spcycle;
                }
            }
        }
    }
    
    int initial = 0;
    for(int i = 0; i < n; i++){
        if(sz(graph[i]) > 2) initial++;
    }
    int ans = 0;
    if(fing_cycles == 0){
      //  cout << initial << endl;
        for(int i = 0; i < n; i++){
            if(special[i]) continue;
            int tmp = initial - (sz(graph[i]) > 2 ? 1 : 0);
            for(auto to : graph[i]){
                if(sz(graph[to]) == 3) tmp--;
            }
            if(!tmp){
                ans++;
                //cout << i << ' ' << sz(graph[i]) << endl;
               // for(auto to : graph[i]){
                   // cout << to << ' ' << sz(graph[to]) << endl;
                //}
                //cout << 'a' << endl;
            }
        }
       // cout << "NO FUCKING CYCLES" << endl;
    }
    else if(initial == 0){
        if(fing_cycles > 1) return 0;
        if(fing_cycles == 1) return saiz;
        return n;
    }
    return ans;
}
/*
7 13
-1
1 2
-1
0 5
-1
2 0
-1
3 2
-1
3 5
-1
4 3
-1
*/

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 2 ms 620 KB Output is correct
3 Correct 3 ms 748 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 2 ms 748 KB Output is correct
6 Correct 3 ms 1132 KB Output is correct
7 Correct 1 ms 492 KB Output is correct
8 Correct 3 ms 748 KB Output is correct
9 Correct 3 ms 876 KB Output is correct
10 Correct 3 ms 748 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 572 ms 35564 KB Output is correct
2 Correct 965 ms 54760 KB Output is correct
3 Correct 1136 ms 83048 KB Output is correct
4 Correct 1148 ms 68588 KB Output is correct
5 Correct 1150 ms 69812 KB Output is correct
6 Correct 1278 ms 114400 KB Output is correct
7 Correct 1112 ms 80484 KB Output is correct
8 Correct 1174 ms 63712 KB Output is correct
9 Correct 1216 ms 69228 KB Output is correct
10 Correct 1081 ms 74092 KB Output is correct

Subtask #3
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 2 ms 620 KB Output is correct
3 Correct 3 ms 748 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 2 ms 748 KB Output is correct
6 Correct 3 ms 1132 KB Output is correct
7 Correct 1 ms 492 KB Output is correct
8 Correct 3 ms 748 KB Output is correct
9 Correct 3 ms 876 KB Output is correct
10 Correct 3 ms 748 KB Output is correct
11 Incorrect 13 ms 748 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 2 ms 620 KB Output is correct
3 Correct 3 ms 748 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 2 ms 748 KB Output is correct
6 Correct 3 ms 1132 KB Output is correct
7 Correct 1 ms 492 KB Output is correct
8 Correct 3 ms 748 KB Output is correct
9 Correct 3 ms 876 KB Output is correct
10 Correct 3 ms 748 KB Output is correct
11 Incorrect 13 ms 748 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #5
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 2 ms 620 KB Output is correct
3 Correct 3 ms 748 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 2 ms 748 KB Output is correct
6 Correct 3 ms 1132 KB Output is correct
7 Correct 1 ms 492 KB Output is correct
8 Correct 3 ms 748 KB Output is correct
9 Correct 3 ms 876 KB Output is correct
10 Correct 3 ms 748 KB Output is correct
11 Correct 572 ms 35564 KB Output is correct
12 Correct 965 ms 54760 KB Output is correct
13 Correct 1136 ms 83048 KB Output is correct
14 Correct 1148 ms 68588 KB Output is correct
15 Correct 1150 ms 69812 KB Output is correct
16 Correct 1278 ms 114400 KB Output is correct
17 Correct 1112 ms 80484 KB Output is correct
18 Correct 1174 ms 63712 KB Output is correct
19 Correct 1216 ms 69228 KB Output is correct
20 Correct 1081 ms 74092 KB Output is correct
21 Incorrect 13 ms 748 KB Output isn't correct
22 Halted 0 ms 0 KB -