Submission #781906

#	Time	Username	Problem	Language	Result	Execution time	Memory
781906		kebine	Naboj (COCI22_naboj)	C++17	110 / 110	403 ms	55280 KiB

naboj

#include<bits/stdc++.h>
#define int long long
#define pii pair<int, int>
using namespace std;
const int MAX=1e18;
signed main() {
  ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  int n, m; cin >> n >> m;
  vector<vector<tuple<int, int, int>>> adj(n);
  stack<pair<int, int>> dfs;
  deque<pair<int, int>> ans;
  vector<int> here(n), away(n);
  vector<bool> used(m), vis(n);
  for(int i=0; i<m; i++) {
    int u, v; cin >> u >> v; --u; --v;
    adj[u].push_back({v, 0, i});
    adj[v].push_back({u, 1, i});
    here[u]++; away[v]++;
  }
  for(int i=0; i<n; i++) {
    if(here[i]==0 && away[i]==0) continue;
    if(here[i]==0) dfs.push({i, 0});
    if(away[i]==0) dfs.push({i, 1});
  }
  while(!dfs.empty()) {
    int u=dfs.top().first, type=dfs.top().second;
    dfs.pop(); vis[u]=1; 
    ans.push_front({u+1, type});
    if(type) {
      for(auto p : adj[u]) {
        used[get<2>(p)]=1;
        int pp=get<0>(p);
        if(vis[pp]) continue;
        away[pp]--;
        if(away[pp]==0 && here[pp]==0) continue;
        if(away[pp]==0) dfs.push({pp, 1}), used[get<2>(p)]=1;
      }
    } else {
      for(auto p : adj[u]) {
        used[get<2>(p)]=1;
        int pp=get<0>(p);
        if(vis[pp]) continue;
        here[pp]--;
        if(here[pp]==0 && away[pp]==0) continue;
        if(here[pp]==0) dfs.push({pp, 0}), used[get<2>(p)]=1;
      }
    }
  }
  for(int i=0; i<m; i++) {
    if(used[i]) continue;
    cout << "-1\n"; return 0;
  }
  cout << ans.size() << '\n';
  for(auto p : ans)
    cout << p.first << ' ' << p.second << '\n';
    return 0;
}

Compilation message (stderr)

naboj.cpp: In function 'int main()':
naboj.cpp:54:3: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   54 |   for(auto p : ans)
      |   ^~~
naboj.cpp:56:5: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   56 |     return 0;
      |     ^~~~~~

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