oj.uz

Submission #527340

# Submission time Handle Problem Language Result Execution time Memory
527340 2022-02-17T09:04:13 Z jamielim Pipes (CEOI15_pipes) C++14
40 / 100
 1458 ms 20360 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;
	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];
			//dont save the edge
		}
	}
	vector<int> comp[n+1];
	for(int i=1;i<=n;i++){
		comp[par2[i]].pb(i);
	}
	// 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=1;i<=n;i++){
		if(SZ(comp[i])>1){
			for(int j=1;j<SZ(comp[i]);j++){
				lca(comp[i][0],comp[i][j]);
			}
		}
	}
	// 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:67:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   67 |   scanf("%d%d",&a,&b);
      |   ~~~~~^~~~~~~~~~~~~~

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 2636 KB Wrong number of edges
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 3404 KB Wrong number of edges
2 Halted 0 ms 0 KB -

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 111 ms 4960 KB Output is correct
2 Correct 142 ms 4952 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 189 ms 7240 KB Output is correct
2 Correct 244 ms 5840 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 348 ms 9840 KB Output is correct
2 Correct 298 ms 10880 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 459 ms 14844 KB Output is correct
2 Correct 374 ms 14432 KB Output is correct

Subtask #7
0 / 10.0

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

Subtask #8
0 / 10.0

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

Subtask #9
0 / 10.0

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

Subtask #10
0 / 10.0

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