Submission #1353527

#	Time	Username	Problem	Language	Result	Execution time	Memory
1353527		julia_08	Sopsug (EGOI23_sopsug)	C++20	50 / 100	204 ms	91256 KiB

Main

#pragma GCC optimize("unroll-loops, O3")

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

const int MAXN = 3e5 + 10;

int deg[MAXN], vis[MAXN];

vector<int> adj[MAXN];

set<int> p[MAXN], not_visited;

vector<pair<int, int>> edges;

bool dfs(int v, bool ans){
  
  vis[v] = 1;
  
  bool ret = true;
  
  for(auto u : adj[v]){
    
    if(vis[u]) return false;
    ret &= dfs(u, ans);
    
    if(ans) edges.push_back({u, v});
    
  }
  
  vector<int> to_visit;
  
  for(auto u : not_visited) if(!p[v].count(u)) to_visit.push_back(u);
  
  for(auto u : to_visit) not_visited.erase(u);
  
  for(auto u : to_visit){
    ret &= dfs(u, ans);
    if(ans) edges.push_back({u, v});
  }
  
  return ret;
  
}

int main(){
  cin.tie(0)->sync_with_stdio(0);
  
  int n, m, k; cin >> n >> m >> k;
  
  while(m--){
    
    int a, b; cin >> a >> b;
    
    adj[b].push_back(a);
    deg[a] ++;
    
  }
  
  while(k--){
    
    int a, b; cin >> a >> b;
    p[b].insert(a);
    
  }
  
  for(int i=0; i<n; i++){
    if(deg[i] > 1){
      cout << "NO\n";
      return 0;
    }
  }
  
  for(int i=0; i<n; i++) if(!deg[i]) not_visited.insert(i);
  
  int root = -1;
  
  for(int i=0; i<n; i++){
    if(not_visited.count(i)){
      
      not_visited.erase(i);
      dfs(i, 0);
      
      root = i;
      
    }
  }
  
  for(int i=0; i<n; i++) if(i != root) if(!deg[i]) not_visited.insert(i);
  
  for(int i=0; i<n; i++) vis[i] = 0;
  
  if(!dfs(root, 1) || !not_visited.empty()){
    cout << "NO\n";
    return 0;
  }
  
  for(auto [a, b] : edges) cout << a << " " << b << "\n";
  
  return 0;
}

Compilation message (stderr)

Main.cpp:1:40: warning: bad option '-f O3' to pragma 'optimize' [-Wpragmas]
    1 | #pragma GCC optimize("unroll-loops, O3")
      |                                        ^
Main.cpp:16:25: warning: bad option '-f O3' to attribute 'optimize' [-Wattributes]
   16 | bool dfs(int v, bool ans){
      |                         ^
Main.cpp:46:10: warning: bad option '-f O3' to attribute 'optimize' [-Wattributes]
   46 | int main(){
      |          ^

• Subtask 0: 0 / 0
• Subtask 1: 12 / 12
• Subtask 2: 10 / 10
• Subtask 3: 0 / 19
• Subtask 4: 0 / 13
• Subtask 5: 17 / 17
• Subtask 6: 11 / 11
• Subtask 7: 0 / 18