oj.uz

Submission #728070

# Submission time Handle Problem Language Result Execution time Memory
728070 2023-04-21T22:54:45 Z n0sk1ll Pipes (CEOI15_pipes) C++17
80 / 100
 1057 ms 65536 KB 
#include <bits/stdc++.h>
 
#define FAST ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);cerr.tie(0)
#define mp make_pair
#define xx first
#define yy second
#define pb push_back
#define pf push_front
#define popb pop_back
#define popf pop_front
#define all(x) x.begin(),x.end()
#define ff(i,a,b) for (int i = a; i < b; i++)
#define fff(i,a,b) for (int i = a; i <= b; i++)
#define bff(i,a,b) for (int i = b-1; i >= a; i--)
#define bfff(i,a,b) for (int i = b; i >= a; i--)
 
using namespace std;
long double typedef ld;
unsigned int typedef ui;
long long int typedef li;
pair<int,int> typedef pii;
pair<li,li> typedef pli;
pair<ld,ld> typedef pld;
vector<vector<int>> typedef graph;
unsigned long long int typedef ull;
//const int mod = 998244353;
const int mod = 1000000007;
 
 
 
 
 
 
 
//Note to self: Check for overflow
 
int up[2][100005];
 
int Up(bool c, int x)
{
    if (up[c][x]<0) return x;
    return up[c][x]=Up(c,up[c][x]);
}
 
bool dsu(bool c, int a, int b)
{
    a=Up(c,a),b=Up(c,b);
    if (a==b) return false;
    if (up[c][a]<up[c][b]) swap(a,b);
    up[c][b]+=up[c][a],up[c][a]=b;
    return true;
}
 
int par[100010];
int idx[100010];
int lowl[100010];
int nt;
vector<int> edge[100010];
 
void dfs(int x){
	idx[x] = lowl[x] = ++nt;
	bool cl = false;
	for(int y:edge[x]){
		if(par[x] == y && !cl){
			cl=true; continue;
		}
		if(!idx[y]){
			par[y]=x;
			dfs(y);
			lowl[x] = min(lowl[x], lowl[y]);
		} else lowl[x] = min(lowl[x], idx[y]);
	}
	if(par[x] && idx[x]==lowl[x]) cout<<x<<" "<<par[x]<<"\n";
}
 
int main()
{
    FAST;
 
    int n,m; cin>>n>>m;
    ff(c,0,2) fff(i,1,n) up[c][i]=-1;
 
    while (m--)
    {
        int u,v; cin>>u>>v;
        if (dsu(0,u,v) || dsu(1,u,v)) edge[u].pb(v),edge[v].pb(u);
    }
 
    fff(i,1,n) if (up[0][i]<0) dfs(i);
}
 
//Note to self: Check for overflow

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 2 ms 2644 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 3156 KB Output is correct
2 Correct 6 ms 2900 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 85 ms 2972 KB Output is correct
2 Correct 82 ms 2836 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 141 ms 3636 KB Output is correct
2 Correct 173 ms 3256 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 244 ms 5228 KB Output is correct
2 Correct 213 ms 4876 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 328 ms 10140 KB Output is correct
2 Correct 296 ms 7572 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 513 ms 11292 KB Output is correct
2 Correct 468 ms 8956 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 627 ms 13336 KB Output is correct
2 Correct 625 ms 9936 KB Output is correct

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 840 ms 13332 KB Output is correct
2 Runtime error 836 ms 62828 KB Memory limit exceeded
3 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 943 ms 12776 KB Output is correct
2 Runtime error 1057 ms 65536 KB Memory limit exceeded
3 Halted 0 ms 0 KB -