oj.uz

Submission #527342

# Submission time Handle Problem Language Result Execution time Memory
527342 2022-02-17T09:10:27 Z jamielim Pipes (CEOI15_pipes) C++14
70 / 100
 1518 ms 17288 KB 
#include <bits/stdc++.h>
using namespace std;

#define fi first
#define se second
#define mp make_pair
#define pb emplace_back
#define ALL(x) x.begin(),x.end()
#define SZ(x) (int)x.size()
typedef long long ll;
typedef pair<int,int> ii;
typedef pair<ii,ii> i4;
const int MOD=1000000007;
const int INF=1012345678;
const ll LLINF=1012345678012345678LL;
const double PI=3.1415926536;
const double EPS=1e-14;

const int MAXN=100005;
int n,m;
int par[MAXN],par2[MAXN];
int root(int x){return par[x]=(par[x]==x?x:root(par[x]));}
int root2(int x){return par2[x]=(par2[x]==x?x:root2(par2[x]));}
vector<int> adj[MAXN]; // only stores a tree

int p[MAXN][18];
bool marking[MAXN][18];
int depth[MAXN];
void dfs(int x,int par){
    if(p[x][0]!=0)return;
    p[x][0]=par;
    if(par!=0)depth[x]=depth[par]+1;
    for(int i:adj[x]){
        if(i==par)continue;
        if(p[i][0]==0)dfs(i,x);
    }
}
void lca(int a,int b){
	//printf("lca %d %d\n",a,b);
    if(a==b)return;// a;
    if(depth[a]<depth[b])swap(a,b);
    for(int i=17;i>=0;i--){
        if(p[a][i]!=0&&depth[p[a][i]]>=depth[b]){
			marking[a][i]=1;
			a=p[a][i];
		}
    }
    if(a==b)return;// a;
    for(int i=17;i>=0;i--){
        if(p[a][i]!=p[b][i]){
			marking[a][i]=1;
			marking[b][i]=1;
			a=p[a][i];
			b=p[b][i];
		}
    }
    marking[a][0]=1;
    marking[b][0]=1;
    return;// p[a][0];
}

int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)par[i]=par2[i]=i;
	int a,b;
	ii edges[n];int idx=0;
	for(int i=0;i<m;i++){
		scanf("%d%d",&a,&b);
		//if a,b are in different trees, merge the two trees
		int ra=root(a),rb=root(b);
		if(ra!=rb){
			par[ra]=rb;
			adj[a].pb(b);
			adj[b].pb(a);
			continue;
		}
		//otherwise, take note that later we have to get rid of the entire cycle
		int r2a=root2(a),r2b=root2(b);
		if(r2a!=r2b){
			par2[r2a]=par2[r2b];
			edges[idx++]=mp(a,b);
		}
	}
	// preprocess the forest
	for(int i=1;i<=n;i++){
		if(depth[i]==0)dfs(i,0);
	}
	for(int i=1;i<18;i++){
        for(int j=1;j<=n;j++){
            p[j][i]=p[p[j][i-1]][i-1];
        }
    }
	
	// for every cycle we want to remove, find the lca, mark all the visited 2kdecomps as gone
	for(int i=0;i<idx;i++){
		lca(edges[i].fi,edges[i].se);
	}
	// then finally propagate all the markings down
	for(int i=17;i>=1;i--){
		for(int j=1;j<=n;j++){
			if(marking[j][i]){
				marking[j][i-1]=1;
				marking[p[j][i-1]][i-1]=1;
			}
		}
	}
	
	for(int i=1;i<=n;i++){
		if(marking[i][0])continue;
		for(int j:adj[i]){
			if(depth[j]<depth[i]){ // j is i's parent
				printf("%d %d\n",j,i);
				break;
			}
		}
	}
}

Compilation message

pipes.cpp: In function 'int main()':
pipes.cpp:63:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   63 |  scanf("%d%d",&n,&m);
      |  ~~~~~^~~~~~~~~~~~~~
pipes.cpp:68:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   68 |   scanf("%d%d",&a,&b);
      |   ~~~~~^~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2640 KB Output is correct
2 Correct 2 ms 2656 KB Output is correct

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 130 ms 3648 KB Output is correct
2 Correct 147 ms 3568 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 179 ms 4436 KB Output is correct
2 Correct 212 ms 4372 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 381 ms 6668 KB Output is correct
2 Correct 263 ms 7232 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 472 ms 12588 KB Output is correct
2 Correct 376 ms 12544 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 729 ms 13988 KB Output is correct
2 Correct 716 ms 14592 KB Output is correct

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 967 ms 17276 KB Memory limit exceeded
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 1169 ms 17288 KB Memory limit exceeded
2 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 1518 ms 16688 KB Memory limit exceeded
2 Halted 0 ms 0 KB -