oj.uz

Submission #733831

# Submission time Handle Problem Language Result Execution time Memory
733831 2023-05-01T10:50:40 Z epicci23 Naboj (COCI22_naboj) C++17
110 / 110
 311 ms 28020 KB 
#include "bits/stdc++.h"
#pragma optimize ("Bismillahirrahmanirrahim")
using namespace std;
#define pb push_back
#define ff first
#define ss second
#define endl "\n" 
#define int long long
#define double long double
#define sz(x) ((int)(x).size())
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define what_is(x) cerr << #x << " is " << x << endl;
//#define m (l+r)/2
constexpr int N=200005;
constexpr int MOD=1000000007;
constexpr int  INF2 = LLONG_MAX;
constexpr int INF=(int)1e18;
constexpr int LOG=30;
typedef pair<int,int> pii;
typedef tuple<int,int,int> tp;
typedef priority_queue<pii,vector<pii>,greater<pii>> min_pq;
typedef priority_queue<pii> max_pq;
typedef long long ll;
//to think//
/*
 * graph approach
 * dp
 * dividing the problem to smaller statements
 * finding the real constraint
 * sqrt decomposition
 * greedy approach
 * pigeonhole principle
 * rewriting the problem/equality 
 * bitwise approaches
 * binary search if monotonic
 * divide and conquer
 * combinatorics
 * inclusion - exclusion
 * think like bfs
*/



inline int in()
{
  int x;cin >> x;
  return x;
}

inline string in2()
{
  string x;cin >> x;
  return x;
}

vector<int> v[N];
bool ok=1;
int vis[N];

void dfs(int c)
{
  if(vis[c]==2) return;
  if(vis[c]==1)
  {
    ok=0;
    return;
  }
  vis[c]=1;
  for(int x:v[c]) dfs(x);
  vis[c]=2;
}

void solve()
{
  int n=in(),m=in();
  
  int freq[n+1];
  memset(freq,0,sizeof(freq));
  for(int i=1;i<=m;i++)
  {
    int a=in(),b=in();
    v[b].pb(a);
    freq[a]++;
  }

  for(int i=1;i<=n;i++) dfs(i);

  if(ok==0)
  {
    cout << -1 << endl;
    return;
  }

  vector<pii> ans;

  queue<int> q;
  for(int i=1;i<=n;i++) if(freq[i]==0) q.push(i);
  

  while(!q.empty())
  {
    int c=q.front();q.pop();
    ans.pb({c,1});
    for(int x:v[c])
    {
      freq[x]--;
      if(freq[x]==0) q.push(x);
    }
  }


  cout << sz(ans) << endl;
  for(auto x:ans) cout << x.ff << " " << x.ss << endl;
}

int32_t main(){
   

     cin.tie(0); ios::sync_with_stdio(0);
     cout << fixed <<  setprecision(15);
   
   int t=1;//cin>> t;
 
 for(int i=1;i<=t;i++)
 {
  //  cout << "Case #" << i << ": ";
    solve();
 }
 
 return 0;
}

Compilation message

naboj.cpp:2: warning: ignoring '#pragma optimize ' [-Wunknown-pragmas]
    2 | #pragma optimize ("Bismillahirrahmanirrahim")
      |

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5024 KB Output is correct
2 Correct 3 ms 4948 KB Output is correct
3 Correct 3 ms 4924 KB Output is correct
4 Correct 3 ms 4948 KB Output is correct
5 Correct 3 ms 4948 KB Output is correct
6 Correct 3 ms 4948 KB Output is correct
7 Correct 4 ms 4948 KB Output is correct
8 Correct 3 ms 5020 KB Output is correct
9 Correct 3 ms 5020 KB Output is correct
10 Correct 3 ms 4948 KB Output is correct
11 Correct 3 ms 4948 KB Output is correct
12 Correct 3 ms 4948 KB Output is correct
13 Correct 3 ms 4948 KB Output is correct
14 Correct 3 ms 4948 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 163 ms 20684 KB Output is correct
2 Correct 133 ms 20568 KB Output is correct
3 Correct 64 ms 13164 KB Output is correct
4 Correct 164 ms 20648 KB Output is correct
5 Correct 135 ms 20668 KB Output is correct
6 Correct 178 ms 20592 KB Output is correct
7 Correct 127 ms 20696 KB Output is correct
8 Correct 110 ms 17476 KB Output is correct
9 Correct 147 ms 20620 KB Output is correct
10 Correct 137 ms 20544 KB Output is correct

Subtask #3
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5024 KB Output is correct
2 Correct 3 ms 4948 KB Output is correct
3 Correct 3 ms 4924 KB Output is correct
4 Correct 3 ms 4948 KB Output is correct
5 Correct 3 ms 4948 KB Output is correct
6 Correct 3 ms 4948 KB Output is correct
7 Correct 4 ms 4948 KB Output is correct
8 Correct 3 ms 5020 KB Output is correct
9 Correct 3 ms 5020 KB Output is correct
10 Correct 3 ms 4948 KB Output is correct
11 Correct 3 ms 4948 KB Output is correct
12 Correct 3 ms 4948 KB Output is correct
13 Correct 3 ms 4948 KB Output is correct
14 Correct 3 ms 4948 KB Output is correct
15 Correct 163 ms 20684 KB Output is correct
16 Correct 133 ms 20568 KB Output is correct
17 Correct 64 ms 13164 KB Output is correct
18 Correct 164 ms 20648 KB Output is correct
19 Correct 135 ms 20668 KB Output is correct
20 Correct 178 ms 20592 KB Output is correct
21 Correct 127 ms 20696 KB Output is correct
22 Correct 110 ms 17476 KB Output is correct
23 Correct 147 ms 20620 KB Output is correct
24 Correct 137 ms 20544 KB Output is correct
25 Correct 179 ms 21636 KB Output is correct
26 Correct 133 ms 18288 KB Output is correct
27 Correct 187 ms 21184 KB Output is correct
28 Correct 267 ms 25372 KB Output is correct
29 Correct 134 ms 16292 KB Output is correct
30 Correct 235 ms 24892 KB Output is correct
31 Correct 28 ms 8044 KB Output is correct
32 Correct 182 ms 22944 KB Output is correct
33 Correct 311 ms 27072 KB Output is correct
34 Correct 167 ms 23212 KB Output is correct
35 Correct 239 ms 27164 KB Output is correct
36 Correct 158 ms 23028 KB Output is correct
37 Correct 218 ms 26108 KB Output is correct
38 Correct 222 ms 24760 KB Output is correct
39 Correct 263 ms 26916 KB Output is correct
40 Correct 233 ms 25476 KB Output is correct
41 Correct 221 ms 25344 KB Output is correct
42 Correct 260 ms 27668 KB Output is correct
43 Correct 174 ms 23564 KB Output is correct
44 Correct 303 ms 28020 KB Output is correct
45 Correct 202 ms 23252 KB Output is correct
46 Correct 255 ms 25544 KB Output is correct