Submission #782195

#	Time	Username	Problem	Language	Result	Execution time	Memory
782195		devariaota	Naboj (COCI22_naboj)	C++17	110 / 110	519 ms	40088 KiB

naboj

#include<bits/stdc++.h>
 
#define sherina ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define pb push_back
#define int long long
#define INF 1e18

using namespace std;

int n , m , a[500005] , b[500005] , jmlhbapa[500005];
vector < int > adj[500005];
vector < pair < int , int > > ans;

void dfs(){
   queue < int > q;
   for(int i = 1 ; i <= n ; i++){
      if(jmlhbapa[i] == 0){
         q.push(i);
         ans.pb(make_pair(i , 0));
      }
   }
   while(!q.empty()){
      int u = q.front(); q.pop();
      //cout << u << endl;
      for(int i : adj[u]){
         jmlhbapa[i]--;
         if(jmlhbapa[i] == 0){
            ans.pb(make_pair(i , 0));
            q.push(i);
         }
      }
   }
}

signed main(){
   cin >> n >> m;
   for(int i = 1 ; i <= m ; i++){
      cin >> a[i] >> b[i];
      adj[a[i]].pb(b[i]);
      jmlhbapa[b[i]]++;
   }
   dfs();
   bool bs = true;
   for(int i = 1 ; i <= n ; i++){
      if(jmlhbapa[i] > 0) bs = false;
   }
   if(!bs){
      cout << "-1" << endl;
      return 0;
   }
   cout << ans.size() << endl;
   for(int i = 0 ; i < ans.size() ; i++){
      cout << ans[i].first << " " << ans[i].second << endl;
   }
}

Compilation message (stderr)

naboj.cpp: In function 'int main()':
naboj.cpp:52:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   52 |    for(int i = 0 ; i < ans.size() ; i++){
      |                    ~~^~~~~~~~~~~~

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