oj.uz

Submission #128228

# Submission time Handle Problem Language Result Execution time Memory
128228 2019-07-10T14:42:29 Z fefe Bridges (APIO19_bridges) C++17
14 / 100
 3000 ms 10472 KB 
#include<bits/stdc++.h>
#define MAX_N 500005
#define MAX_M 1000005
#define fi first
#define se second
#define pb push_back
#define eb emplace_back
#define all(v) (v).begin(),(v).end()
using namespace std;
typedef long long LL;
typedef long double LD;
typedef pair<int,int> pii;
typedef pair<LL,LL> pil;
struct edge{
	int x,y,v;
}E[MAX_M],Q[MAX_M];
struct node{
	int t,i,b,a;
};
struct infor{
	int x,y,hx,hy,ex,ey;
};
int n,m;
int qn;
int par[MAX_N],height[MAX_N],ea[MAX_N];
bool chk[MAX_M];
const int b=50000;
vector<edge> e;
vector<node> lst;
vector<pii> ans;
stack<infor> st;
int find_par(int x){return par[x]==x?x:find_par(par[x]);}
void init(){
	for(int i=1;i<=n;i++){
		par[i]=i;
		height[i]=ea[i]=1;
	}
}
int merge(int x,int y){
	int p=find_par(x);
	int q=find_par(y);
	if(p==q)	return 0;
	st.push({p,q,height[p],height[q],ea[p],ea[q]});
	if(height[p]>height[q]){
		ea[p]+=ea[q];
		par[q]=p;
	}else{
		if(height[p]==height[q])	height[q]++;
		ea[q]+=ea[p];
		par[p]=q;
	}
	return 1;
}
void _back(int cnt){
	while(st.size() && cnt--){
		infor p = st.top();
		par[p.x]=p.x;par[p.y]=p.y;
		height[p.x]=p.hx;height[p.y]=p.hy;
		ea[p.x]=p.ex;ea[p.y]=p.ey;
		st.pop();
	}
	while(st.size())	st.pop();
}
void solve(int k){
	for(int i=1;i<=m;i++)	chk[i]=false;
	for(int i=0;i<qn;i++){
		if(Q[i].v==1){
			chk[Q[i].x]=true;
			lst.pb({i,Q[i].x,E[Q[i].x].v,Q[i].y});
			Q[i].v=-1;
		}else	Q[i].v=i;
	}
	e.clear();e.resize(0);
	for(int i=1;i<=m;i++){
		if(!chk[i])	e.pb(E[i]);
	}
	sort(Q,Q+qn,[&](const edge x,const edge y){
		if(x.v==-1)		return false;
		if(y.v==-1)	return true;
		return (x.y>y.y);
	});
	sort(all(e),[&](const edge x,const edge y){return x.v>y.v;});
	init();
	int p=0;
	for(int i=0;i<qn;i++){
		edge ques = Q[i];
		if(ques.v==-1)	break;
		int cn=0;
		for(;p<e.size() && e[p].v>=ques.y;p++)	merge(e[p].x,e[p].y);
		
		for(node ne:lst){
			int x=E[ne.i].x;
			int y=E[ne.i].y;
			int v;
			if(ne.t>ques.v)	v=ne.b;
			else	v=ne.a;
			
			if(v>=ques.y)	cn+=merge(x,y);
		}
		ans.pb({k+ques.v,ea[find_par(ques.x)]});
		_back(cn);
	}
	for(node ne:lst)	E[ne.i].v=ne.a;
	qn=0;
}
int main(){
	int i;
	scanf("%d %d",&n,&m);
	for(i=1;i<=m;i++)	scanf("%d %d %d",&E[i].x,&E[i].y,&E[i].v);
	int q;scanf("%d",&q);
	for(i=1;i<=q;i++){
		scanf("%d %d %d",&Q[qn].v,&Q[qn].x,&Q[qn].y);qn++;
		if(qn==b)	solve(i);
	}
	solve(i);
	sort(all(ans));
	for(pii print:ans)	printf("%d\n",print.se);
	return 0;
}

Compilation message

bridges.cpp: In function 'void solve(int)':
bridges.cpp:89:9: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(;p<e.size() && e[p].v>=ques.y;p++) merge(e[p].x,e[p].y);
        ~^~~~~~~~~
bridges.cpp: In function 'int main()':
bridges.cpp:108:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d",&n,&m);
  ~~~~~^~~~~~~~~~~~~~~
bridges.cpp:109:25: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(i=1;i<=m;i++) scanf("%d %d %d",&E[i].x,&E[i].y,&E[i].v);
                    ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
bridges.cpp:110:13: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  int q;scanf("%d",&q);
        ~~~~~^~~~~~~~~
bridges.cpp:112:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d %d",&Q[qn].v,&Q[qn].x,&Q[qn].y);qn++;
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Incorrect 417 ms 888 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 16.0

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

Subtask #3
0 / 17.0

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

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 156 ms 6256 KB Output is correct
2 Correct 69 ms 3540 KB Output is correct
3 Correct 60 ms 5272 KB Output is correct
4 Correct 49 ms 5364 KB Output is correct
5 Correct 115 ms 8544 KB Output is correct
6 Correct 162 ms 10120 KB Output is correct
7 Correct 116 ms 8756 KB Output is correct
8 Correct 112 ms 7036 KB Output is correct
9 Correct 115 ms 7136 KB Output is correct
10 Correct 116 ms 7676 KB Output is correct
11 Correct 136 ms 8732 KB Output is correct
12 Correct 145 ms 8936 KB Output is correct
13 Correct 135 ms 9324 KB Output is correct
14 Correct 116 ms 9168 KB Output is correct
15 Correct 114 ms 8936 KB Output is correct
16 Correct 157 ms 9976 KB Output is correct
17 Correct 160 ms 9960 KB Output is correct
18 Correct 157 ms 10080 KB Output is correct
19 Correct 170 ms 10060 KB Output is correct
20 Correct 144 ms 9800 KB Output is correct
21 Correct 146 ms 9704 KB Output is correct
22 Correct 154 ms 10472 KB Output is correct
23 Correct 110 ms 8552 KB Output is correct

Subtask #5
0 / 13.0

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

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Incorrect 417 ms 888 KB Output isn't correct
4 Halted 0 ms 0 KB -