oj.uz

Submission #1114679

# Submission time Handle Problem Language Result Execution time Memory
1114679 2024-11-19T11:12:15 Z SalihSahin Povjerenstvo (COI22_povjerenstvo) C++14
13 / 100
 598 ms 157968 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);
      }
   }

   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.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 211 ms 157732 KB Output is correct
2 Correct 184 ms 137332 KB Output is correct
3 Correct 12 ms 45392 KB Output is correct
4 Correct 84 ms 95968 KB Output is correct
5 Correct 147 ms 123892 KB Output is correct
6 Correct 175 ms 121212 KB Output is correct
7 Correct 146 ms 126808 KB Output is correct
8 Correct 186 ms 122748 KB Output is correct
9 Correct 351 ms 136452 KB Output is correct
10 Correct 490 ms 129040 KB Output is correct
11 Correct 482 ms 131092 KB Output is correct
12 Correct 506 ms 125868 KB Output is correct
13 Correct 373 ms 127248 KB Output is correct
14 Correct 309 ms 127500 KB Output is correct
15 Correct 289 ms 127760 KB Output is correct
16 Correct 244 ms 127820 KB Output is correct
17 Correct 58 ms 54208 KB Output is correct
18 Correct 65 ms 59720 KB Output is correct

Subtask #2
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 209 ms 157968 KB Output is correct
2 Correct 174 ms 118152 KB Output is correct
3 Correct 150 ms 124416 KB Output is correct
4 Correct 474 ms 130568 KB Output is correct
5 Incorrect 598 ms 131744 KB For each person outside the committee there should be someone in the committee who they dislike.
6 Halted 0 ms 0 KB -

Subtask #3
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 46364 KB Output is correct
2 Correct 17 ms 46204 KB Output is correct
3 Correct 13 ms 46064 KB Output is correct
4 Correct 16 ms 46296 KB Output is correct
5 Incorrect 18 ms 46324 KB For each person outside the committee there should be someone in the committee who they dislike.
6 Halted 0 ms 0 KB -

Subtask #4
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 211 ms 157732 KB Output is correct
2 Correct 184 ms 137332 KB Output is correct
3 Correct 12 ms 45392 KB Output is correct
4 Correct 84 ms 95968 KB Output is correct
5 Correct 147 ms 123892 KB Output is correct
6 Correct 175 ms 121212 KB Output is correct
7 Correct 146 ms 126808 KB Output is correct
8 Correct 186 ms 122748 KB Output is correct
9 Correct 351 ms 136452 KB Output is correct
10 Correct 490 ms 129040 KB Output is correct
11 Correct 482 ms 131092 KB Output is correct
12 Correct 506 ms 125868 KB Output is correct
13 Correct 373 ms 127248 KB Output is correct
14 Correct 309 ms 127500 KB Output is correct
15 Correct 289 ms 127760 KB Output is correct
16 Correct 244 ms 127820 KB Output is correct
17 Correct 58 ms 54208 KB Output is correct
18 Correct 65 ms 59720 KB Output is correct
19 Correct 209 ms 157968 KB Output is correct
20 Correct 174 ms 118152 KB Output is correct
21 Correct 150 ms 124416 KB Output is correct
22 Correct 474 ms 130568 KB Output is correct
23 Incorrect 598 ms 131744 KB For each person outside the committee there should be someone in the committee who they dislike.
24 Halted 0 ms 0 KB -