Submission #705043

#	Time	Username	Problem	Language	Result	Execution time	Memory
705043		Paul_Liao_1457	Naboj (COCI22_naboj)	C++17	110 / 110	230 ms	15120 KiB

naboj

//記得跳題
//#pragma GCC optimize("O4,unroll_loops")
//#pragma GCC target("avx2")
#include<iostream>
#include<array>
#include<vector>
#include<string>
#include<algorithm>
#include<set>
#include<queue>
#include<stack>
#include<math.h>
#include<map>
#include<unordered_map>
#include<unordered_set>
#include<cstring>
#include<iomanip>
#include<bitset>
#include<tuple>
#include<random>
 
#define ll long long
#define FOR(i,a,b) for(int i=a;i<b;i++)
#define pb push_back
#define INF (ll)(2e18)
#define F first
#define S second
#define endl "\n"
#define AC ios::sync_with_stdio(0);
 
using namespace std;

int n, m;
int in[200005];
vector<int> e[200005];
vector<pair<int, int> > ans;

signed main(){
  AC;
  cin >> n >> m;
  FOR (i, 0, m) {
    int a, b; cin >> a >> b;
    in[b]++;
    e[a].pb(b);
  }
  
  queue<int> Q;
  FOR (i, 1, n+1) if (!in[i]) {
    Q.push(i);
  }
  
  int cnt = 0;
  while (Q.size()) {
    int now = Q.front(); Q.pop();
    ans.pb({now, 0});
    cnt++;
    for (auto i:e[now]) {
      in[i]--;
      if (!in[i]) {
        Q.push(i);
      }
    }
  }
  
  if (cnt != n) {
    cout << -1 << endl;
  } else {
    cout << ans.size() << endl;
    for (auto i:ans) {
      cout << i.F << " " << i.S << endl;
    }
  }
  
}

• Subtask 1: 15 / 15
• Subtask 2: 25 / 25
• Subtask 3: 70 / 70