Submission #782538

#	Time	Username	Problem	Language	Result	Execution time	Memory
782538		gun_gan	Naboj (COCI22_naboj)	C++17	110 / 110	167 ms	16152 KiB

naboj

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int MX = 2e5 + 5;

int N, M;
int deg[MX];
vector<int> g[MX];

int main() {
      cin.tie(0); ios_base::sync_with_stdio(0);

      cin >> N >> M;
      for(int i = 0; i < M; i++) {
            int u, v;
            cin >> u >> v;
            g[v].push_back(u);
            deg[u]++;
      }

      queue<int> q;
      vector<int> ord;
      for(int i = 1; i <= N; i++) {
            if(!deg[i]) {
                  q.push(i);
            }
      }

      int cnt = 0;
      while(!q.empty()) {
            auto v = q.front(); q.pop();
            cnt++;

            for(auto u : g[v]) {
                  deg[u]--;
                  if(!deg[u]) {
                        q.push(u);
                        ord.push_back(u);
                  }
            }
      }

      if(cnt < N) {
            cout << -1 << '\n';
            return 0;
      }

      cout << ord.size() << '\n';
      for(auto x : ord) {
            cout << x << " " << 1 << '\n';
      }
}     

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