Submission #1024921

#TimeUsernameProblemLanguageResultExecution timeMemory
1024921gs25Untitled (POI11_kon)C++17
0 / 100
839 ms72752 KiB
#include <bits/stdc++.h> using namespace std; const int MAXN = 5010; bool adj[MAXN][MAXN]; int scc[MAXN]; int deg[MAXN]; int n; /* if(adj[i][j]==0){ g[i].push_back(j+n); rg[j+n].push_back(i); } else{ g[i+n].push_back(j); rg[j].push_back(i+n); } */ bool vis[MAXN*2]; stack<int> st; void dfs(int i){ if(vis[i]) return; vis[i] = 1; if(i<=n){ for(int j=1; j<=n; j++) if(j!=i && adj[i][j]==0 && !vis[j+n]) dfs(j+n); } else { for(int j=1; j<=n; j++) if(j!=i && adj[i-n][j]==1 && !vis[j]) dfs(j); } /* for(auto ne:g[i]){ if(!vis[ne]) dfs(ne); } */ st.push(i); } void dfs1(int i, int pv){ if(vis[i]) return; vis[i] = 1; scc[i] = pv; if(i<=n){ for(int j=1; j<=n; j++) if(j!=i && adj[i][j] && !vis[j+n]) dfs(j+n); } else { for(int j=1; j<=n; j++) if(j!=i && !adj[i-n][j] && !vis[j]) dfs(j); } /* for(auto ne:rg[i]){ if(!vis[ne]) dfs1(ne,pv); } */ } int main(void){ ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); cin >> n; int a = 0; for(int i=1; i<=n; i++){ int x; cin >> x; a+=x; while(x--){ int j; cin >> j; adj[i][j] = 1; } } if(a==0 || a== n*(n+1)){ cout << n; return 0; } /* for(int i=1; i<=n; i++){ for(int j=1; j<=n; j++){ if(j==i) continue; if(adj[i][j]==0){ g[i].push_back(j+n); rg[j+n].push_back(i); } else{ g[i+n].push_back(j); rg[j].push_back(i+n); } } } */ for(int i=1; i<=n*2; i++) if(!vis[i]) dfs(i); for(int i=1; i<=n*2; i++) vis[i] = 0; int pv = 0; while(!st.empty()){ int t = st.top(); st.pop(); if(!vis[t]) dfs1(t,pv++); } vector<int> c, nc; for(int i=1; i<=n; i++){ if(scc[i]==scc[i+n]) { cout << 0; return 0; } if(scc[i]<scc[i+n]) nc.push_back(i); else c.push_back(i); } assert(c.size()!=0 && nc.size()!=0); //for(auto x : c) cerr << x << " "; for(auto x : c){ for(auto y : nc){ if(adj[x][y]) deg[x]++, deg[y]++; } } int ans = 1; for(auto n : c) if(deg[n]==0) ans++; for(auto n : nc) if(deg[n]==c.size()) ans++; for(auto n : c){ for(auto nn : nc){ int p = deg[n] - adj[n][nn], q = deg[nn] - adj[n][nn]; if(p==0 && q==c.size()-1) ans++; } } cout << ans; }

Compilation message (stderr)

kon.cpp: In function 'int main()':
kon.cpp:115:29: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  115 |   for(auto n : nc) if(deg[n]==c.size()) ans++;
      |                       ~~~~~~^~~~~~~~~~
kon.cpp:119:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  119 |       if(p==0 && q==c.size()-1) ans++;
      |                  ~^~~~~~~~~~~~
#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...
#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...