oj.uz

Submission #647872

# Submission time Handle Problem Language Result Execution time Memory
647872 2022-10-04T10:22:53 Z mychecksedad Political Development (BOI17_politicaldevelopment) C++17
4 / 100
 16 ms 24204 KB 
/* Author : Mychecksdead */
#include<bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
typedef long long int ll;
typedef long double ld;
#define MOD (1000000000+7)
#define MOD1 (998244353)
#define PI 3.1415926535
#define pb push_back
#define setp() cout << setprecision(15)
#define all(x) x.begin(), x.end()
#define oset tree<int, null_type,less_equal<int>, rb_tree_tag,tree_order_statistics_node_update>
#define debug(x) cerr << #x << " is " << x << '\n';
const int N = 1e6+100, M = 1e5+10, F = 2147483646, K = 20;


int n, k;
vector<int> g[N], path;
vector<bool> vis(N);
void dfs(int v, int p){
    vis[v] = 1;
    path.pb(v);
    for(int u: g[v]){
        if(u != p){
            if(vis[u]){
                if(path[path.size() - 3] == u){
                    cout << 3;
                    exit(0);
                }
            }else{
                dfs(u, v);
            }
        }    
    }
    path.pop_back();
}

void solve(){
    cin >> n >> k;
    for(int i = 0; i < n; ++i){
        int d; cin >> d;
        for(int j = 0; j < d; ++j){
            int x; cin >> x; g[i].pb(x);
        }
    }
    if(k <= 2){
        for(int i = 0; i < n; ++i){
            if(g[i].size()){
                cout << 2;
                return;
            }
        }
        cout << 1;
        return;
    }
    if(k <= 3){
        for(int i = 0; i < n; ++i) dfs(i, i);
        for(int i = 0; i < n; ++i){
            if(g[i].size()){
                cout << 2;
                return;
            }
        }
        cout << 1;
    }
}   





int main(){
    cin.tie(0); ios::sync_with_stdio(0);
    int T = 1, aa;
    // cin >> T;aa=T;
    while(T--){
        // cout << "Case #" << aa-T << ": ";
        solve();
        cout << '\n';
    }
    return 0;
 
}

Compilation message

politicaldevelopment.cpp: In function 'int main()':
politicaldevelopment.cpp:76:16: warning: unused variable 'aa' [-Wunused-variable]
   76 |     int T = 1, aa;
      |                ^~

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 23892 KB Output is correct
2 Correct 13 ms 23884 KB Output is correct
3 Correct 14 ms 24044 KB Output is correct
4 Correct 13 ms 24096 KB Output is correct
5 Correct 14 ms 24016 KB Output is correct
6 Correct 13 ms 24120 KB Output is correct
7 Correct 14 ms 24020 KB Output is correct
8 Correct 12 ms 23932 KB Output is correct
9 Correct 16 ms 23868 KB Output is correct
10 Correct 16 ms 23888 KB Output is correct

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 23892 KB Output is correct
2 Correct 13 ms 23884 KB Output is correct
3 Correct 14 ms 24044 KB Output is correct
4 Correct 13 ms 24096 KB Output is correct
5 Correct 14 ms 24016 KB Output is correct
6 Correct 13 ms 24120 KB Output is correct
7 Correct 14 ms 24020 KB Output is correct
8 Correct 12 ms 23932 KB Output is correct
9 Correct 16 ms 23868 KB Output is correct
10 Correct 16 ms 23888 KB Output is correct
11 Correct 15 ms 24204 KB Output is correct
12 Incorrect 15 ms 24156 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #3
0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 13 ms 23892 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 23892 KB Output is correct
2 Correct 13 ms 23884 KB Output is correct
3 Correct 14 ms 24044 KB Output is correct
4 Correct 13 ms 24096 KB Output is correct
5 Correct 14 ms 24016 KB Output is correct
6 Correct 13 ms 24120 KB Output is correct
7 Correct 14 ms 24020 KB Output is correct
8 Correct 12 ms 23932 KB Output is correct
9 Correct 16 ms 23868 KB Output is correct
10 Correct 16 ms 23888 KB Output is correct
11 Correct 15 ms 24204 KB Output is correct
12 Incorrect 15 ms 24156 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 23892 KB Output is correct
2 Correct 13 ms 23884 KB Output is correct
3 Correct 14 ms 24044 KB Output is correct
4 Correct 13 ms 24096 KB Output is correct
5 Correct 14 ms 24016 KB Output is correct
6 Correct 13 ms 24120 KB Output is correct
7 Correct 14 ms 24020 KB Output is correct
8 Correct 12 ms 23932 KB Output is correct
9 Correct 16 ms 23868 KB Output is correct
10 Correct 16 ms 23888 KB Output is correct
11 Correct 15 ms 24204 KB Output is correct
12 Incorrect 15 ms 24156 KB Output isn't correct
13 Halted 0 ms 0 KB -