#include <bits/stdc++.h>
#define N 500050
#define f first
#define s second
using namespace std;
typedef pair<int, int> pii;
int n, m, block[N], cnt = 0, usado[N], prox[N], id = 1;
vector<pii> grafo[N];
vector<int> path[N];
inline bool dfs(int x, int &ini, int &f)
{
usado[x] = id;
for(int i = 0; i < grafo[x].size(); i++)
{
auto v = grafo[x][i];
if(block[v.s])
{
swap(grafo[x][i], grafo[x].back());
grafo[x].pop_back();
i --;
continue;
}
if(v.f == ini and !block[v.s])
{
block[v.s] = 1;
prox[x] = -1;
swap(grafo[x][i], grafo[x].back());
grafo[x].pop_back();
return true;
}
if(usado[v.f] == id or block[v.s]) continue;
if(dfs(v.f, ini, f))
{
prox[x] = v.f;
block[v.s] = 1;
swap(grafo[x][i], grafo[x].back());
grafo[x].pop_back();
return true;
}
}
return false;
}
int main()
{
ios::sync_with_stdio(false); cin.tie(0);
cin>>n>>m;
for(int i = 1, a, b; i <= m; i++)
{
cin>>a>>b;
grafo[a].push_back({b, i});
grafo[b].push_back({a, i});
}
for(int x = 1; x <= n; x++) random_shuffle(grafo[x].begin(), grafo[x].end());
for(int x = 1; x <= n; x++)
{
for(int i = 0; i < grafo[x].size(); i++)
{
auto v = grafo[x][i];
if(block[v.s])
{
swap(grafo[x][i], grafo[x].back());
grafo[x].pop_back();
i --;
continue;
}
++id;
usado[x] = id;
block[v.s] = 1;
swap(grafo[x][i], grafo[x].back());
grafo[x].pop_back();
i --;
path[cnt].push_back(x);
if(dfs(v.f, x, cnt))
{
int u = v.f;
while(u != -1)
{
path[cnt].push_back(u);
u = prox[u];
}
++ cnt;
}
}
}
for(int i = 0; i < cnt; i++)
{
for(auto x: path[i]) cout<<x<<" ";
cout<<"\n";
}
}
Compilation message
postmen.cpp: In function 'bool dfs(int, int&, int&)':
postmen.cpp:18:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < grafo[x].size(); i++)
~~^~~~~~~~~~~~~~~~~
postmen.cpp: In function 'int main()':
postmen.cpp:84:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < grafo[x].size(); i++)
~~^~~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
25 ms |
23808 KB |
Output is correct |
2 |
Correct |
22 ms |
23808 KB |
Output is correct |
3 |
Correct |
19 ms |
23808 KB |
Output is correct |
4 |
Correct |
27 ms |
23936 KB |
Output is correct |
5 |
Correct |
20 ms |
23912 KB |
Output is correct |
6 |
Correct |
20 ms |
24064 KB |
Output is correct |
7 |
Correct |
27 ms |
24424 KB |
Output is correct |
8 |
Correct |
20 ms |
24064 KB |
Output is correct |
9 |
Correct |
65 ms |
27000 KB |
Output is correct |
10 |
Correct |
23 ms |
24040 KB |
Output is correct |
11 |
Correct |
22 ms |
24064 KB |
Output is correct |
12 |
Correct |
76 ms |
27488 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
24 ms |
23912 KB |
Output is correct |
2 |
Correct |
23 ms |
23808 KB |
Output is correct |
3 |
Correct |
25 ms |
23784 KB |
Output is correct |
4 |
Correct |
25 ms |
23988 KB |
Output is correct |
5 |
Correct |
19 ms |
23936 KB |
Output is correct |
6 |
Correct |
25 ms |
23988 KB |
Output is correct |
7 |
Correct |
33 ms |
24448 KB |
Output is correct |
8 |
Correct |
22 ms |
24040 KB |
Output is correct |
9 |
Correct |
57 ms |
26988 KB |
Output is correct |
10 |
Correct |
26 ms |
24064 KB |
Output is correct |
11 |
Correct |
22 ms |
24064 KB |
Output is correct |
12 |
Correct |
67 ms |
27700 KB |
Output is correct |
13 |
Correct |
127 ms |
34008 KB |
Output is correct |
14 |
Execution timed out |
1091 ms |
29772 KB |
Time limit exceeded |
15 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
17 ms |
23808 KB |
Output is correct |
2 |
Correct |
24 ms |
23820 KB |
Output is correct |
3 |
Correct |
20 ms |
23912 KB |
Output is correct |
4 |
Correct |
20 ms |
23988 KB |
Output is correct |
5 |
Correct |
18 ms |
23936 KB |
Output is correct |
6 |
Correct |
19 ms |
24064 KB |
Output is correct |
7 |
Correct |
26 ms |
24540 KB |
Output is correct |
8 |
Correct |
20 ms |
24192 KB |
Output is correct |
9 |
Correct |
75 ms |
27104 KB |
Output is correct |
10 |
Correct |
20 ms |
24064 KB |
Output is correct |
11 |
Correct |
24 ms |
24064 KB |
Output is correct |
12 |
Correct |
66 ms |
27768 KB |
Output is correct |
13 |
Correct |
110 ms |
33940 KB |
Output is correct |
14 |
Execution timed out |
1088 ms |
29792 KB |
Time limit exceeded |
15 |
Halted |
0 ms |
0 KB |
- |