Submission #439544

#	Time	Username	Problem	Language	Result	Execution time	Memory
439544		K4YAN	Political Development (BOI17_politicaldevelopment)	C++17	16 / 100	3076 ms	108180 KiB

politicaldevelopment

//Be Name Khoda
// 10:55 -> 10:50 shoroo
// 12:40 | 12:40
 
#include<bits/stdc++.h>
 
using namespace std;
 
typedef long long ll;
typedef long double ld;
#define all(x) x.begin(), x.end()
#define pll pair<ll, ll>
#define pii pair<int, int>
#define plll pair<pll, ll>
#define piii pair<pii, int>
#define piiii pair<pii, pii>
 
const short int mxn = 5e3 + 1;
int n, k, q, w;
short int v, deg[mxn];
vector<int> dp[mxn][11];
vector<short int> kmk, g2[11];
vector<vector<short int>> g[11];
bool edge[mxn][mxn];
 
void input() {
 
    int tmp = 0;
    cin >> n >> k;
    for(short int i = 0; i < n; i++) {
        cin >> q;
        deg[i] = q;
        for(short int j = 0; j < q; j++) {
            cin >> v;
            edge[v][i] = 1;
            if(i < v) {
                dp[i][2].push_back(tmp);
                dp[v][2].push_back(tmp++);
                g[2].push_back({i, v});
                if(deg[i] < deg[v]) {
                    g2[2].push_back(i);
                }
                else {
                    g2[2].push_back(v);
                }
            }
        }
    }
 
}
 
void solve() {
 
    bool b;
    int tmp;
    vector<short int> u;
    for(int i = 3; i <= k; i++) {
        tmp = 0;
 
        for(int j = 0; j < n; j++) {
 
            for(w = 0; w < (int)(g[i - 1].size()); w++) {
                
                if(edge[j][g2[i - 1][w]] == false) {
                    continue;
                }
                b = true;
                for(auto e : g[i - 1][w]) {
 
                    if(edge[j][e] == false) {
                        b = false;
                        break;
                    }
 
                }
 
                if(b == false) {
                    continue;
                }
                for(auto e : u) {
                    kmk.push_back(e);
                    dp[e][i].push_back(tmp);
                }
                dp[j][i].push_back(tmp++);
                kmk.push_back(j);
                g[i].push_back(kmk);
                if(deg[g2[i - 1][w]] > deg[j]) {
                    g2[i].push_back(j);
                }
                else {
                    g2[i].push_back(g2[i - 1][w]);
                }
                kmk.clear();
            }
        }
        if(int(g[i].size()) == 0) {
            break;
        }
    }
 
    for(short int i = 2; i <= k; i++) {
        if(int(g[i].size()) == 0) {
            cout << i - 1 << endl;
            return;
        }
    }
    cout << k << endl;
    return;
 
}
 
int main() {
 
    ios_base::sync_with_stdio(false);
 
    input(), solve();
 
    return 0;
 
}

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