| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 152724 |
2019-09-09T09:47:29 Z |
toloraia |
Pipes (CEOI15_pipes) |
C++17 |
|
5000 ms |
65540 KB |
#include <bits/stdc++.h>
#define F first
#define S second
#define mp make_pair
#define pb push_back
#define ll long long
//#define ll __int128
#define LEFT(a) ((a)<<1)
#define RIGHT(a) (LEFT(a) + 1)
#define MID(a,b) ((a+b)>>1)
#define MAX(a,b) ((a)>(b)?(a):(b))
#define MIN(a,b) ((a)<(b)?(a):(b))
/*
#pragma comment(linker, "/STACK: 20000000005")
#pragma GCC optimize("Ofast")
#pragma GCC target("avx2,fma")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
*/
using namespace std;
const int N = 1e5 + 5, M = 6e6 + 5;
int n, m;
ll K;
vector < ll > G[N], GG[N];
vector < int > g[N];
ll A[N], AA[N];
int B[N], BB[N];
int x, y;
int T;
int in[N], up[N];
void dfs (int k, int p){
in[k] = ++T;
up[k] = in[k];
int to, i, toto;
ll X;
int num = (int)G[k].size();
for (i = 0; i < num; i++){
X = G[k][i];
while (X){
toto = X % K;
X /= K;
to = toto;
if (to > n)
to -= n;
if (to == p)
continue;
if (in[to]){
up[k] = min (up[k], in[to]);
continue;
}
dfs (to, k);
if (up[to] > in[k]){
cout << k << " " << to << endl;
}
up[k] = min (up[k], up[to]);
}
}
num = (int)GG[k].size();
for (i = 0; i < num; i++){
X = GG[k][i];
while (X){
toto = X % K;
X /= K;
to = toto;
if (to > n)
to -= n;
if (to == p)
continue;
if (in[to]){
up[k] = min (up[k], in[to]);
continue;
}
dfs (to, k);
up[k] = min (up[k], up[to]);
}
}
}
vector < int > V;
int t, num;
ll X;
int j;
int i, to;
main()
{
//freopen ("in.in", "r", stdin);freopen ("out.out", "w", stdout);
//ios_base::sync_with_stdio(false);
cin >> n >> m;
K = n + 1;
for (i = 1; i <= m; i++){
cin >> x >> y;
if (x > y)
swap (x, y);
g[x].pb (y);
}
for (i = 1; i <= n; i++){
sort (g[i].begin(), g[i].end());
num = (int)g[i].size();
for (j = 0; j < g[i].size(); j++){
if (j && g[i][j] == g[i][j - 1])
continue;
to = g[i][j];
y = to;
x = i;
if (j + 1 < num && g[i][j] == g[i][j + 1]){
AA[i] = AA[i] * K + y;
BB[i]++;
if (BB[i] == 4){
BB[i] = 0;
GG[i].pb (AA[i]);
AA[i] = 0;
}
AA[to] = AA[to] * K + x;
BB[to]++;
if (BB[to] == 4){
BB[to] = 0;
GG[to].pb (AA[to]);
AA[to] = 0;
}
}
else {
A[i] = A[i] * K + y;
B[i]++;
if (B[i] == 4){
B[i] = 0;
G[i].pb (A[i]);
A[i] = 0;
}
A[to] = A[to] * K + x;
B[to]++;
if (B[to] == 4){
B[to] = 0;
G[to].pb (A[to]);
A[to] = 0;
}
}
}
}
for (i = 1; i <= n; i++)
if (A[i])
G[i].pb (A[i]);
for (i = 1; i <= n; i++)
if (AA[i])
G[i].pb (AA[i]);
for (i = 1; i <= n; i++)
if (in[i] == 0)
dfs (i, 0);
return 0;
}
Compilation message
pipes.cpp:94:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
main()
^
pipes.cpp: In function 'int main()':
pipes.cpp:109:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (j = 0; j < g[i].size(); j++){
~~^~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
7416 KB |
Output is correct |
| 2 |
Incorrect |
8 ms |
7416 KB |
Wrong number of edges |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
22 ms |
8100 KB |
Output is correct |
| 2 |
Incorrect |
21 ms |
7800 KB |
Wrong number of edges |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
587 ms |
15736 KB |
Output is correct |
| 2 |
Correct |
580 ms |
14148 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1055 ms |
20292 KB |
Memory limit exceeded (if you are sure your verdict is not MLE, please contact us) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1782 ms |
30060 KB |
Memory limit exceeded (if you are sure your verdict is not MLE, please contact us) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
2429 ms |
65536 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
3777 ms |
65536 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
4989 ms |
65540 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
5088 ms |
38156 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
5062 ms |
37736 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
