Submission #954580

#TimeUsernameProblemLanguageResultExecution timeMemory
954580koukirocksPolitical Development (BOI17_politicaldevelopment)C++17
4 / 100
2 ms3420 KiB
#include <bits/stdc++.h> #define speed ios_base::sync_with_stdio(0); cin.tie(0) #define all(x) (x).begin(),(x).end() #define F first #define S second //#pragma GCC optimize("O3") //#pragma GCC target("avx,avx2") //#pragma GCC target("popcnt") namespace{using namespace std;} typedef long long ll; typedef double db; typedef long double ldb; typedef pair<int,int> pii; typedef pair<ll,ll> pll; const ll MAX=1e5+10,P=1e9+7; const ll INF=0x3f3f3f3f,oo=0x3f3f3f3f3f3f3f3f; const ldb eps=1e-6; int n,k; vector<int> G[MAX]; int deg[MAX]; bool vis[MAX]; bool findc(int lim) { queue<int> BFS; for (int i=0;i<n;i++) { if (deg[i]<lim) { BFS.push(i); // cout<<lim<<" "<<i<<" "<<deg[i]<<" i\n"; } } int cnt=0; while (!BFS.empty()) { cnt++; int v=BFS.front(); BFS.pop(); for (int i:G[v]) { if (deg[i]--==lim) BFS.push(i); } } for (int i=0;i<n;i++) deg[i]=G[i].size(); // cout<<lim<<" "<<cnt<<"\n"; return (cnt!=n); } int main() { speed; cin>>n>>k; for (int i=0;i<n;i++) { int d; cin>>d; deg[i]=d; while (d--) { int x; cin>>x; G[i].push_back(x); } } // for (int i=0;i<n;i++) cout<<deg[i]<<" "; // cout<<"\n"; for (int i=1;i<k;i++) { if (!findc(i)) { cout<<i<<"\n"; return 0; } } cout<<k<<"\n"; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...