oj.uz

답안 #1006691

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1006691 2024-06-24T07:19:31 Z SyedSohaib_123 Pipes (CEOI15_pipes) C++17
0 / 100
 531 ms 65536 KB 
#include<bits/stdc++.h>



using namespace std;



#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx")



#define str string
#define append push_back
#define vi vector<int>
#define int long long
#define yes cout<<"YES"<<endl;
#define no cout<<"NO"<<endl;
#define endl '\n'
#define all(ls) ls.begin(),ls.end()
#define sorted(ls) sort(ls.begin(),ls.end());
#define reversed(ls) reverse(ls.begin(),ls.end());
#define print(n) for(auto i:n)cout<<i<<' ';cout<<endl;
#define input(n,ls,m) vector<n>ls(m);for(int i=0;i<m;i++)cin>>ls[i];
#define len(s) s.size()
#define ff first
#define ss second
int const N=1e5+10;



int mod=1e9+7;
int mod1=998244353;



int sum_(vector<int>ls){int s=1;for(auto i:ls){s+=i;}return s;}
int min(int a,int b){if (a>b){return b;}return a;}
int max(int a,int b){if (a<b){return b;}return a;}



//......................................tHe ReaL cOdE beGinS HerE....................................../



map<int,bool>visited;
vector<int> graph[N],g[N];
int stree[N],cnt[N],par[N];
int ans=0;
int n;
set<pair<int,int>>s;



void dfs_(int node,int pa){
	if(visited[node]) return;visited[node]=1;
	for(auto i:g[node]){
		int m=visited[i];
		dfs_(i,node);
		cnt[node]+=cnt[i];
		if(!m and !cnt[i]){
			s.insert({node,i});
		}
	}
}



void dfs(int node,int pa){
	if(visited[node]) return;
	visited[node]=1;
	auto it=s.find({pa,node});
	par[node]=pa;
	if(pa!=-1){
		g[pa].append(node);
	}
	if(it!=s.end()) {
		s.erase(it);
		s.erase(s.find({node,pa}));
	}
	stree[node]=1;
	for(auto i:graph[node]){
		auto m=visited[i];
		dfs(i,node);
		if(!m) stree[node]+=stree[i];
	}
}




void solve(){
	int m;
	cin>>n>>m;
	ans=(n*(n-1))/2;
	for(int i=1;i<=n;i++) g[i].clear(),graph[i].clear(),stree[i]=cnt[i]=par[i]=0;
	visited.clear();
	s.clear();
	for(int i=0;i<m;i++){
		int u,v;
		cin>>u>>v;
		s.insert({u,v});
		s.insert({v,u});
		graph[u].append(v);
		graph[v].append(u);
	}
	for(int i=1;i<=n;i++){
		if(visited[i]) continue;
		dfs(i,-1);
	}
	for(auto [node,pa]:s){
		if(stree[pa]<stree[node]) swap(node,pa);
		cnt[pa]--;
		cnt[node]++;
	}
	s.clear();
	visited.clear();
	for(int i=1;i<=n;i++){
		if(visited[i])continue;
		dfs_(i,-1);
	}
	for(auto [i,j]:s){
		cout<<i<<' '<<j<<endl;
	}
}



signed main(){
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	int t=1;
	// cin>>t;
	while(t--)
		solve();
}

Compilation message

pipes.cpp: In function 'void dfs_(long long int, long long int)':
pipes.cpp:59:2: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   59 |  if(visited[node]) return;visited[node]=1;
      |  ^~
pipes.cpp:59:27: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   59 |  if(visited[node]) return;visited[node]=1;
      |                           ^~~~~~~

Subtask #1
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 7260 KB Output is correct
2 Incorrect 1 ms 7260 KB Wrong number of edges
3 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 16 ms 9564 KB Output is correct
2 Incorrect 15 ms 9112 KB Wrong number of edges
3 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 483 ms 65536 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 490 ms 65536 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 489 ms 65536 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 488 ms 65536 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 522 ms 65536 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 479 ms 65536 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 510 ms 65536 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 531 ms 65536 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -