Submission #666752

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
666752	2022-11-29 14:03:22	neki	Naboj (COCI22_naboj)	C++14	110 / 110	563 ms	41904 KiB

naboj

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#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]){
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

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