oj.uz

Submission #1114677

# Submission time Handle Problem Language Result Execution time Memory
1114677 2024-11-19T11:03:33 Z SalihSahin Povjerenstvo (COI22_povjerenstvo) C++14
0 / 100
 212 ms 160540 KB 
#include <bits/stdc++.h>
#define pb push_back
using namespace std;
 
const int N = 5e5 + 5;

vector<int> adj[N*2], adjrev[N], vis(N), comp(N), col(N);
vector<int> nodes;
vector<vector<int> > group[2];

void dfs(int node){
   vis[node] = 1;
   for(auto itr: adj[node]){
      if(!vis[itr]){
         dfs(itr);
      }
   }
   nodes.pb(node);
}

void dfs2(int node, int compcnt, int color){
   vis[node] = 1;
   comp[node] = compcnt;
   col[node] = color;
   group[col[node]][compcnt].pb(node);

   for(auto itr: adjrev[node]){
      if(!vis[itr]){
         dfs2(itr, compcnt, (color^1));
      }
   }
}


int main(){
   ios_base::sync_with_stdio(false);
   cin.tie(0); cout.tie(0);
   int n, m;
   cin>>n>>m;
   vector<pair<int, int> > edge(m);
   for(int i = 0; i < m; i++){
      int u, v;
      cin>>u>>v;
      edge[i] = {u, v};
      adj[u].pb(v);
      adjrev[v].pb(u);
   }

   for(int i = 1; i <= n; i++){
      if(!vis[i]){
         dfs(i);
      }
   }
   reverse(nodes.begin(), nodes.end());
   for(int i = 0; i <= n; i++) vis[i] = 0;

   vector<int> v;
   int compcnt = 0;
   for(auto itr: nodes){
      if(!vis[itr]){
         group[0].pb(v);
         group[1].pb(v);
         dfs2(itr, compcnt, 0);
         compcnt++;
      }
   }

   for(int i = 1; i <= n; i++){
      adj[i].clear(); 
   } // memory israf etme

   for(int i = 0; i < m; i++){
      int fnode = comp[edge[i].first] * 2 + col[edge[i].first];
      int snode = comp[edge[i].second] * 2 + col[edge[i].second];
      adj[fnode].pb(snode);
   }

   vector<int> ans;
   vector<int> take(N*2, 0); // 0 = ?, 1 aldık, -1 alamayız
   take[(compcnt - 1) * 2 + 1] = 1; // son sccnin 1 ini almayı dene
   for(auto itr: group[1][compcnt-1]) ans.pb(itr);
   take[(compcnt - 1) * 2] = -1;
   for(int i = compcnt-2; i >= 0; i--){
      int node0 = i*2, node1 = i*2+1;

      for(auto itr: adj[node0]){
         if(take[itr] == 1) take[node0] = -1;
      }
      for(auto itr: adj[node1]){
         if(take[itr] == 1) take[node1] = -1;
      }

      if(take[node0] == -1 && take[node1] == -1) continue;

      if(take[node0] == -1){
         take[node1] = 1;
         for(auto itr: group[1][i]) ans.pb(itr);
      }
      else{
         take[node0] = 1;
         for(auto itr: group[0][i]) ans.pb(itr);
      }
   }

   cout<<ans.size()<<endl;
   for(auto itr: ans){
      cout<<itr<<" ";
   }
   cout<<endl;
   return 0;
}

Subtask #1
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 212 ms 160528 KB Output is correct
2 Correct 203 ms 140048 KB Output is correct
3 Incorrect 13 ms 45392 KB K cannot be 0
4 Halted 0 ms 0 KB -

Subtask #2
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 209 ms 160540 KB Output is correct
2 Incorrect 192 ms 120200 KB For each person outside the committee there should be someone in the committee who they dislike.
3 Halted 0 ms 0 KB -

Subtask #3
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 46552 KB Output is correct
2 Incorrect 13 ms 46040 KB For each person outside the committee there should be someone in the committee who they dislike.
3 Halted 0 ms 0 KB -

Subtask #4
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 212 ms 160528 KB Output is correct
2 Correct 203 ms 140048 KB Output is correct
3 Incorrect 13 ms 45392 KB K cannot be 0
4 Halted 0 ms 0 KB -