Submission #666752

#	Time	Username	Problem	Language	Result	Execution time	Memory
666752		neki	Naboj (COCI22_naboj)	C++14	110 / 110	563 ms	41904 KiB

naboj

#include <bits/stdc++.h>
#define ll long long
#define vc vector

using namespace std;

int main() {
    ll n, m;cin >> n >> m;
    vc<vc<ll>> out(n+1), in(n+1);
    for(ll i=0;i<m;++i){
        ll a, b;cin >> a >> b;
        out[a].push_back(b);
        in[b].push_back(a);
    }
    
    vc<ll> cntin(n+1, 0), cntout(n+1, 0);
    for(ll i=1;i<=n;++i) cntin[i]=in[i].size(), cntout[i]=out[i].size();
    queue<ll> q;
    vc<ll> vis(n+1, 0), ch(n+1, 0);
    for(ll i=1;i<=n;++i) if(cntin[i]==0 or cntout[i]==0) vis[i]=1, ch[i]=(cntin[i]==0)? 1LL:0LL, q.push(i);//, cout <<i << " ";cout << endl;
    
    vc<ll> ans;
    while(q.size()){
        ll u=q.front();q.pop();
        ans.emplace_back(u);
        for(auto v: in[u])if(!vis[v]){
            --cntout[v];
            if(cntin[v]==0 or cntout[v]==0) q.push(v), ch[v]=(cntin[v]==0)? 1LL:0LL, vis[v]=1;
        }
        for(auto v: out[u])if(!vis[v]){
            --cntin[v];
            if(cntin[v]==0 or cntout[v]==0) q.push(v), ch[v]=(cntout[v]==0)? 0LL:1LL, vis[v]=1;
        }
    }
    if(ans.size()==n){
        cout << ans.size()<< endl;
        reverse(ans.begin(), ans.end());
        for(auto v: ans) cout << v << " " << ch[v] <<'\n';
    }
    else cout << -1 <<endl;
}

Compilation message (stderr)

naboj.cpp: In function 'int main()':
naboj.cpp:35:18: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
   35 |     if(ans.size()==n){
      |        ~~~~~~~~~~^~~

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