Submission #441675

#	Time	Username	Problem	Language	Result	Execution time	Memory
441675		Mahfel	Political Development (BOI17_politicaldevelopment)	C++17	4 / 100	7 ms	844 KiB

politicaldevelopment

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MXN = 5002;
vector<int> adj[MXN];
int h[MXN];
bool k3,mark[MXN];
 
void DFS(int v , int dad) {
    mark[v] = 1;
    h[v] = (dad == -1 ? 0 : h[dad]+1);
    vector<int> be;
    for(auto u : adj[v]) {
        if(mark[u]) {
            if(h[u] == h[v]-2) k3 = 1;
            be.push_back(h[u]);
            continue;
        }
        DFS(u , v);
    }
 
    sort(be.begin() , be.end());
    for(int i = 1 ; i < be.size() ; i++) {
        if(be[i]-be[i-1] == 1) {
            k3 = 1; break;
        }
    }
}
 
int main() {
 
    int n,m = 0,k; cin >> n >> k;
    for(int i = 0 ; i < n ; i++) {
        int d; cin >> d; m += d;
        for(int j = 0 ; j < d ; j++) {
            int u; cin >> u;
            adj[i].push_back(u);
        }
    }
    m /= 2;
    for(int i = 0 ; i < n ; i++) {
        if(mark[i]) continue;
        DFS(i , -1);
    }
    if(k3) {
        cout << "3\n"; return 0;
    }
 
    if(m > 0) {
        cout << "2\n";
    } else {
        cout << "1\n";
    }
 
}

Compilation message (stderr)

politicaldevelopment.cpp: In function 'void DFS(int, int)':
politicaldevelopment.cpp:23:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   23 |     for(int i = 1 ; i < be.size() ; i++) {
      |                     ~~^~~~~~~~~~~

• Subtask 1: 4 / 4
• Subtask 2: 0 / 12
• Subtask 3: 0 / 23
• Subtask 4: 0 / 38
• Subtask 5: 0 / 23