Submission #1024929

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1024929	2024-07-16T12:42:40 Z	gs25	Conspiracy (POI11_kon)	C++17	70 / 100	762 ms	67152 KB

#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-n && 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]) dfs1(j+n,pv); 
  }
  else {
    for(int j=1; j<=n; j++) if(j!=i-n && !adj[i-n][j] && !vis[j]) dfs1(j,pv); 
  }
  /*
  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){
    for(auto y : nc){
      if(adj[x][y]) deg[x]++, deg[y]++; 
    }
  }
  int ans = 1; 
  for(auto n1 : c) if(deg[n1]==0) ans++; 
  for(auto n1 : nc) if(deg[n1]==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

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

Subtask #1
0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	344 KB	Output is correct
2	Correct	1 ms	348 KB	Output is correct
3	Runtime error	1 ms	604 KB	Execution killed with signal 6
4	Halted	0 ms	0 KB	-

Subtask #2
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	1 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct

Subtask #3
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	604 KB	Output is correct
2	Correct	1 ms	604 KB	Output is correct
3	Correct	1 ms	604 KB	Output is correct

Subtask #4
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	860 KB	Output is correct
2	Correct	2 ms	1368 KB	Output is correct
3	Correct	2 ms	860 KB	Output is correct

Subtask #5
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3 ms	1116 KB	Output is correct
2	Correct	3 ms	1628 KB	Output is correct
3	Correct	2 ms	1116 KB	Output is correct

Subtask #6
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	13 ms	7092 KB	Output is correct
2	Correct	42 ms	9920 KB	Output is correct
3	Correct	153 ms	20852 KB	Output is correct

Subtask #7
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	19 ms	8540 KB	Output is correct
2	Correct	58 ms	13080 KB	Output is correct
3	Correct	202 ms	27216 KB	Output is correct

Subtask #8
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	71 ms	15700 KB	Output is correct
2	Correct	124 ms	21904 KB	Output is correct
3	Correct	316 ms	39504 KB	Output is correct

Subtask #9
0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	139 ms	24548 KB	Output is correct
2	Incorrect	276 ms	38484 KB	Output isn't correct
3	Halted	0 ms	0 KB	-

Subtask #10
0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	762 ms	67152 KB	Output is correct
2	Incorrect	433 ms	52308 KB	Output isn't correct
3	Halted	0 ms	0 KB	-