Submission #1114679

#	Time	Username	Problem	Language	Result	Execution time	Memory
1114679		SalihSahin	Povjerenstvo (COI22_povjerenstvo)	C++14	13 / 100	598 ms	157968 KiB

Main

#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);
      }
   }

   bool check = 1;
   vector<int> inans(n+1), hehas(n+1);
   for(auto itr: ans) inans[itr] = 1;
   for(int i = 0; i < m; i++){
      if(inans[edge[i].first] && inans[edge[i].second]) check = 0;
      if(!inans[edge[i].first] && inans[edge[i].second]) hehas[edge[i].first] = 1;
   }
   for(int i = 1; i <= n; i++){
      if(inans[i] == 0 && hehas[i] == 0) check = 0;
   }
   if(ans.size() == 0) check = 0;

   if(check){
      cout<<ans.size()<<endl;
      for(auto itr: ans){
         cout<<itr<<" ";
      }
      cout<<endl;
   }
   else{
      for(int i = 0; i < 2*N; i++) take[i] = 0;
      ans.clear();

      take[(compcnt - 1) * 2 + 1] = -1; // son sccnin 1 ini almayı dene
      for(auto itr: group[0][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: 13 / 13
• Subtask 2: 0 / 21
• Subtask 3: 0 / 33
• Subtask 4: 0 / 33