oj.uz

Submission #243907

# Submission time Handle Problem Language Result Execution time Memory
243907 2020-07-02T06:23:41 Z errorgorn Pipes (CEOI15_pipes) C++14
40 / 100
 5000 ms 65536 KB 
//雪花飄飄北風嘯嘯
//天地一片蒼茫
 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/rope>
using namespace std;
using namespace __gnu_pbds;
using namespace __gnu_cxx;
#define ll long long
#define ii pair<ll,ll>
#define iii pair<ii,ll>
#define fi first
#define se second
#define endl '\n'
#define debug(x) cout << #x << " is " << x << endl;
 
#define rep(x,start,end) for(auto x=(start)-((start)>(end));x!=(end)-((start)>(end));((start)<(end)?x++:x--))
#define all(x) (x).begin(),(x).end()
#define sz(x) (int)(x).size()
 
ll MAX(ll a){return a;}
ll MIN(ll a){return a;}
template<typename... Args>
ll MAX(ll a,Args... args){return max(a,MAX(args...));}
template<typename... Args>
ll MIN(ll a,Args... args){return min(a,MIN(args...));}
 
#define indexed_set tree<ll,null_type,less<ll>,rb_tree_tag,tree_order_statistics_node_update>
 
mt19937 rng(chrono::system_clock::now().time_since_epoch().count());
 

struct ufds{
    int p[100005];
    int r[100005];

    ufds(){
        for (int x=0;x<100005;x++){
            p[x]=x;
            r[x]=0;
        }
    }
    int parent(int i){return (p[i]==i)?i:p[i]=parent(p[i]);}
    void unions(int i,int j){
        i=parent(i),j=parent(j);
        if (i==j) return;
        if (r[i]<r[j]){
            p[i]=j;
        }
        else{
            p[j]=i;
            if (r[i]==r[j]) r[i]++;
        }
    }
}dsu=ufds();

struct node{
	int s,e,m;
	bool val=false;
	node *l,*r;
	
	node (int _s,int _e){
		s=_s,e=_e,m=s+e>>1;
		
		if (s!=e){
			l=new node(s,m);
			r=new node(m+1,e);
		}
	}
	
	void update(int i,int j){
		if (s==i && e==j) val=true;
		else if (j<=m) l->update(i,j);
		else if (m<i) r->update(i,j);
		else l->update(i,m),r->update(m+1,j);
	}
	
	bool query(int i){
		if (val) return true;
		else if (s==e) return false;
		else if (i<=m && l->query(i)) return true;
		else if (m<i && r->query(i)) return true;
		else return false;
	}
} *root=new node(0,100005);


int n,m;
vector<int> al[100005];
int in[100005]; //preorder
int st[100005]; //subtree size
int parent[100005]; //first parent
int hparent[100005]; //parent on heavy path
int depth[100005];
void dfs_st(int i,int p){
    parent[i]=p;
    st[i]=1;
    if (al[i][0]==p && al[i].size()>1) swap(al[i][0],al[i][1]);
    for (auto &it:al[i]){ ///& is important here
        if (it==p) continue;
        depth[it]=depth[i]+1;
        dfs_st(it,i);
        st[i]+=st[it];
        if (st[it]>st[al[i][0]]){
            swap(it,al[i][0]);
            //we ensure heavy child is al[i][0]
        }
    }
}

int dfs_time=0;
void dfs_hld(int i,int p){
    in[i]=++dfs_time;
    for (auto it:al[i]){
        if (it==p) continue;
        hparent[it]=(it==al[i][0])?hparent[i]:it;
        dfs_hld(it,i);
    }
}

void hld_query(int i,int j){
    while (hparent[i]!=hparent[j]){
        if (depth[hparent[i]]<depth[hparent[j]]) swap(i,j);
		//cerr<<"debug: "<<in[hparent[i]]<<" "<<in[i]<<endl;
        root->update(in[hparent[i]],in[i]);
        i=parent[hparent[i]];
    }
    if (in[i]>in[j]) swap(i,j);
	//cerr<<"debug: "<<in[i]+1<<" "<<in[j]<<endl;
    if (in[i]!=in[j]) root->update(in[i]+1,in[j]);
}

 
vector<int> span;

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	
	cin>>n>>m;
	
	int a,b;
	rep(x,0,m){
		cin>>a>>b;
		
		if (dsu.parent(a)!=dsu.parent(b)){
			al[a].push_back(b);
			al[b].push_back(a);
			
			dsu.unions(a,b);
			span.push_back(x);
		}
	}
	
	rep(x,1,n+1) if (!depth[x]){
		depth[x]=1;
		parent[x]=0;
		hparent[x]=1;
		if (!al[x].empty()){
   			dfs_st(x,-1);
    		dfs_hld(x,-1);
		}
	}
	
	//rep(x,1,n+1) cout<<x<<" "<<in[x]<<endl;
	
	cin.seekg(0, ios::beg);
	
	int idx=0;
	
	cin>>n>>m;
	rep(x,0,m){
		cin>>a>>b;
		
		if (idx!=sz(span) && span[idx]==x){
			idx++;
			continue;
		}
		else{
			hld_query(a,b);
		}
	}
	
	rep(x,1,n+1) if (depth[x]!=1){
		if (!root->query(in[x])) cout<<x<<" "<<parent[x]<<endl;
	}
	
}

Compilation message

pipes.cpp: In constructor 'node::node(int, int)':
pipes.cpp:65:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   s=_s,e=_e,m=s+e>>1;
               ~^~

Subtask #1
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 598 ms 13056 KB Output is correct
2 Correct 522 ms 13176 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1240 ms 13432 KB Output is correct
2 Correct 1270 ms 13408 KB Output is correct

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2332 ms 14200 KB Output is correct
2 Runtime error 1905 ms 28556 KB Memory limit exceeded (if you are sure your verdict is not MLE, please contact us)

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 4209 ms 16720 KB Memory limit exceeded (if you are sure your verdict is not MLE, please contact us)
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5080 ms 26480 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5072 ms 62128 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5075 ms 65536 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5096 ms 65536 KB Time limit exceeded
2 Halted 0 ms 0 KB -