| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 703313 |
2023-02-27T01:39:38 Z |
willychan |
Naboj (COCI22_naboj) |
C++14 |
|
304 ms |
25920 KB |
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
//#include<bits/extc++.h>
//__gnu_pbds
const int N = 2e5+5;
int in[N];
int out[N];
vector<int> side[N];
bool vis[N];
int main(){
ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0);
int n,m;cin>>n>>m;
for(int i=0;i<m;i++){
int a,b;cin>>a>>b;
in[a]++;
out[b]++;
side[a].push_back(b);
side[b].push_back(a);
}
queue<int> q;
for(int i=1;i<=n;i++){
if(min(in[i],out[i])==0){
q.push(i);
vis[i]=1;
}
}
vector<pair<int,int> > ans;
while(q.size()) {
int cur = q.front();
q.pop();
if(in[cur]) ans.push_back({cur,1});
else ans.push_back({cur,0});
for(auto i : side[cur]){
if(vis[i]) continue;
if(in[cur]){
out[i]--;
}else{
in[i]--;
}
if(min(in[i],out[i])==0){
q.push(i);
vis[i]=1;
}
}
}
for(int i=1;i<=n;i++){
if(!vis[i]){
cout<<-1<<"\n";
return 0;
}
}
cout<<ans.size()<<"\n";
for(int i=(int)ans.size()-1;i>=0;i--){
cout<<ans[i].first<<" "<<ans[i].second<<"\n";
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
4948 KB |
Output is correct |
| 2 |
Correct |
2 ms |
5044 KB |
Output is correct |
| 3 |
Correct |
3 ms |
4948 KB |
Output is correct |
| 4 |
Correct |
2 ms |
4948 KB |
Output is correct |
| 5 |
Correct |
3 ms |
4948 KB |
Output is correct |
| 6 |
Correct |
3 ms |
5040 KB |
Output is correct |
| 7 |
Correct |
3 ms |
5036 KB |
Output is correct |
| 8 |
Correct |
3 ms |
5040 KB |
Output is correct |
| 9 |
Correct |
3 ms |
5036 KB |
Output is correct |
| 10 |
Correct |
3 ms |
4948 KB |
Output is correct |
| 11 |
Correct |
2 ms |
5040 KB |
Output is correct |
| 12 |
Correct |
3 ms |
4948 KB |
Output is correct |
| 13 |
Correct |
2 ms |
4972 KB |
Output is correct |
| 14 |
Correct |
2 ms |
4948 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
134 ms |
19668 KB |
Output is correct |
| 2 |
Correct |
143 ms |
19624 KB |
Output is correct |
| 3 |
Correct |
65 ms |
12712 KB |
Output is correct |
| 4 |
Correct |
153 ms |
19752 KB |
Output is correct |
| 5 |
Correct |
137 ms |
19816 KB |
Output is correct |
| 6 |
Correct |
141 ms |
19644 KB |
Output is correct |
| 7 |
Correct |
142 ms |
19824 KB |
Output is correct |
| 8 |
Correct |
99 ms |
16440 KB |
Output is correct |
| 9 |
Correct |
144 ms |
19736 KB |
Output is correct |
| 10 |
Correct |
156 ms |
19684 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
4948 KB |
Output is correct |
| 2 |
Correct |
2 ms |
5044 KB |
Output is correct |
| 3 |
Correct |
3 ms |
4948 KB |
Output is correct |
| 4 |
Correct |
2 ms |
4948 KB |
Output is correct |
| 5 |
Correct |
3 ms |
4948 KB |
Output is correct |
| 6 |
Correct |
3 ms |
5040 KB |
Output is correct |
| 7 |
Correct |
3 ms |
5036 KB |
Output is correct |
| 8 |
Correct |
3 ms |
5040 KB |
Output is correct |
| 9 |
Correct |
3 ms |
5036 KB |
Output is correct |
| 10 |
Correct |
3 ms |
4948 KB |
Output is correct |
| 11 |
Correct |
2 ms |
5040 KB |
Output is correct |
| 12 |
Correct |
3 ms |
4948 KB |
Output is correct |
| 13 |
Correct |
2 ms |
4972 KB |
Output is correct |
| 14 |
Correct |
2 ms |
4948 KB |
Output is correct |
| 15 |
Correct |
134 ms |
19668 KB |
Output is correct |
| 16 |
Correct |
143 ms |
19624 KB |
Output is correct |
| 17 |
Correct |
65 ms |
12712 KB |
Output is correct |
| 18 |
Correct |
153 ms |
19752 KB |
Output is correct |
| 19 |
Correct |
137 ms |
19816 KB |
Output is correct |
| 20 |
Correct |
141 ms |
19644 KB |
Output is correct |
| 21 |
Correct |
142 ms |
19824 KB |
Output is correct |
| 22 |
Correct |
99 ms |
16440 KB |
Output is correct |
| 23 |
Correct |
144 ms |
19736 KB |
Output is correct |
| 24 |
Correct |
156 ms |
19684 KB |
Output is correct |
| 25 |
Correct |
160 ms |
18596 KB |
Output is correct |
| 26 |
Correct |
161 ms |
19968 KB |
Output is correct |
| 27 |
Correct |
174 ms |
20720 KB |
Output is correct |
| 28 |
Correct |
219 ms |
22748 KB |
Output is correct |
| 29 |
Correct |
135 ms |
19120 KB |
Output is correct |
| 30 |
Correct |
213 ms |
22576 KB |
Output is correct |
| 31 |
Correct |
23 ms |
7492 KB |
Output is correct |
| 32 |
Correct |
155 ms |
20008 KB |
Output is correct |
| 33 |
Correct |
270 ms |
25160 KB |
Output is correct |
| 34 |
Correct |
168 ms |
20136 KB |
Output is correct |
| 35 |
Correct |
259 ms |
25200 KB |
Output is correct |
| 36 |
Correct |
150 ms |
19832 KB |
Output is correct |
| 37 |
Correct |
250 ms |
23960 KB |
Output is correct |
| 38 |
Correct |
203 ms |
22084 KB |
Output is correct |
| 39 |
Correct |
267 ms |
24864 KB |
Output is correct |
| 40 |
Correct |
232 ms |
23112 KB |
Output is correct |
| 41 |
Correct |
229 ms |
22960 KB |
Output is correct |
| 42 |
Correct |
286 ms |
25752 KB |
Output is correct |
| 43 |
Correct |
185 ms |
20568 KB |
Output is correct |
| 44 |
Correct |
304 ms |
25920 KB |
Output is correct |
| 45 |
Correct |
167 ms |
20148 KB |
Output is correct |
| 46 |
Correct |
226 ms |
23100 KB |
Output is correct |
