oj.uz

Submission #750854

# Submission time Handle Problem Language Result Execution time Memory
750854 2023-05-30T11:49:29 Z edogawa_something Povjerenstvo (COI22_povjerenstvo) C++17
0 / 100
 249 ms 41312 KB 
#include<bits/stdc++.h>
#include<chrono>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef long double ld;
typedef string str;
typedef bool bl;
typedef vector<ll> vii;
typedef pair<ll,ll> pii;
typedef vector<pii> vpi;
#define ordered_set tree<pii,null_type,less<pii>,rb_tree_tag,tree_order_statistics_node_update>
#define fast ios_base::sync_with_stdio(0);cin.tie();
#define test ll qqqqq;cin>>qqqqq;while(qqqqq--)
#define test1 ll qqqqq=1;while(qqqqq--)
#define F first
#define S second
#define forn(i,n) for(int i=0;i<n;i++)
#define forx(i,j,n) for(int i=j;i<n;i++)
#define pb push_back
#define eb emplace_back
#define pob pop_back
#define all(v) v.begin(),v.end()
#define lb lower_bound
#define ub upper_bound
#define pow powww
#define prtll(x) printf("%lld",x)
#define prtld(x) printf("%Lf",x)
#define prtst(x) printf("%s",x)
#define prtch(x) printf("%c",x)
#define measure chrono::high_resolution_clock::now()
#define duration chrono::duration_cast<chrono::milliseconds>(end-start)
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
const ll dx[]{1,0,-1,0,1,-1,1,-1};
const ll dy[]{0,-1,0,1,1,-1,-1,1};
const ll inf=1e18;
const ll mod=1e9+7;
const ll LM=1e8+1;
const ll M=5e5+10;
const ll MM=4002;
const ll MMM=501;
const ld pi=acos(-1);
//const ll mod=998244353;
ll pow(ll r,ll to,ll m=mod){
  ll res=1;
  r%=m;
  while(to){
    if((to&1)){
      res*=r,res%=m;
    }
    r*=r,r%=m;
    to=(to>>1);
  }
  return res;
}
ll n,m,mp[M];
vii v[M];
bl vis[M];
ll col[M];
ll inv(ll x){
  if(x==1)
  return 2;
  else
  return 1;
}
int main(){
  fast
  //freopen("gen.txt","r",stdin);
  auto start=measure;
  test1{
    cin>>n>>m;
    forn(i,m){
      ll x,y;
      cin>>x>>y;
      v[y].pb(x);
      mp[x]=1;
    }
    queue<ll>q;
    forx(i,1,n+1){
      if(!mp[i])
      q.push(i),col[i]=1;
    }
    while(!q.empty()){
      ll r=q.front();
      q.pop();
      for(auto it:v[r]){
        if(vis[it])
        continue;
        vis[it]=1;
        col[it]=inv(col[r]);
        q.push(it);
      }
    }
    vii ans;
    forx(i,1,n+1){
      if(col[i]==1)
      ans.pb(i);
    }
    cout<<ans.size()<<'\n';
    for(auto it:ans)
    cout<<it<<' ';
  }
  auto end=measure;
  auto dur=duration;
  //cout<<fixed<<dur.count()<<'\n';
  return 0;
}
/*
*/

Subtask #1
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 158 ms 38980 KB Output is correct
2 Correct 145 ms 38920 KB Output is correct
3 Correct 7 ms 11988 KB Output is correct
4 Correct 51 ms 26648 KB Output is correct
5 Correct 93 ms 34196 KB Output is correct
6 Correct 132 ms 40820 KB Output is correct
7 Correct 93 ms 28540 KB Output is correct
8 Correct 153 ms 38520 KB Output is correct
9 Correct 249 ms 34032 KB Output is correct
10 Incorrect 175 ms 40052 KB There must not be two people within the committee such that one person dislikes the other.
11 Halted 0 ms 0 KB -

Subtask #2
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 134 ms 38732 KB Output is correct
2 Correct 154 ms 41312 KB Output is correct
3 Correct 88 ms 27568 KB Output is correct
4 Incorrect 241 ms 36704 KB There must not be two people within the committee such that one person dislikes the other.
5 Halted 0 ms 0 KB -

Subtask #3
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 12348 KB Output is correct
2 Correct 8 ms 12372 KB Output is correct
3 Correct 7 ms 12248 KB Output is correct
4 Incorrect 9 ms 12328 KB There must not be two people within the committee such that one person dislikes the other.
5 Halted 0 ms 0 KB -

Subtask #4
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 158 ms 38980 KB Output is correct
2 Correct 145 ms 38920 KB Output is correct
3 Correct 7 ms 11988 KB Output is correct
4 Correct 51 ms 26648 KB Output is correct
5 Correct 93 ms 34196 KB Output is correct
6 Correct 132 ms 40820 KB Output is correct
7 Correct 93 ms 28540 KB Output is correct
8 Correct 153 ms 38520 KB Output is correct
9 Correct 249 ms 34032 KB Output is correct
10 Incorrect 175 ms 40052 KB There must not be two people within the committee such that one person dislikes the other.
11 Halted 0 ms 0 KB -