제출 #382637

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
382637		Kerim	다리 (APIO19_bridges)	C++17	59 / 100	3077 ms	203940 KiB

bridges

#include "bits/stdc++.h"
#define MAXN 100009
#define INF 1000000007
#define mp(x,y) make_pair(x,y)
#define all(v) v.begin(),v.end()
#define pb(x) push_back(x)
#define wr cout<<"----------------"<<endl;
#define ppb() pop_back()
#define tr(ii,c) for(__typeof((c).begin()) ii=(c).begin();ii!=(c).end();ii++)
#define ff first
#define ss second
#define my_little_dodge 46
#define debug(x)  cerr<< #x <<" = "<< x<<endl;
using namespace std;

typedef long long ll;
typedef pair<int,int> PII;
template<class T>bool umin(T& a,T b){if(a>b){a=b;return 1;}return 0;}
template<class T>bool umax(T& a,T b){if(a<b){a=b;return 1;}return 0;}
const int BLOK=350;
pair<PII,int>edge[MAXN];
pair<int,PII>query[MAXN];
int ans[MAXN],ata[MAXN],sz[MAXN];
bool ban[MAXN],ban1[MAXN];
stack<int>st;
vector<pair<PII,int> >history;
int tap(int x){
	if(ata[x]==x)return x;
	return tap(ata[x]);	
}
bool merge(PII v){
	int x=tap(v.ff),y=tap(v.ss);
	if(x==y)return 0;
	if(sz[x]<sz[y])swap(x,y);
	history.pb(mp(mp(x,y),sz[y]));
	ata[y]=x;sz[x]+=sz[y]; return 1;	
}
int main(){
    //freopen("file.in", "r", stdin);
    int n,m;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++){
    	int u,v,w;
		scanf("%d%d%d",&u,&v,&w);
		edge[i]=mp(mp(u,v),w);
    }
    int q;
    scanf("%d",&q);
    for(int i=1;i<=q;i++){
    	int t,a,b;
		scanf("%d%d%d",&t,&a,&b);
		query[i]=mp(t,mp(a,b));	
    }
    for(int i=1;i<=q;i+=BLOK){
    	memset(ban,0,sizeof ban);
    	for(int i=1;i<=n;i++)ata[i]=i,sz[i]=1;
    	vector<PII>v,g;int r=min(i+BLOK-1,q);
    	for(int j=i;j<=r;j++){
    		if(query[j].ff==1)
    			ban[query[j].ss.ff]=j;
    		else
    			g.pb(mp(query[j].ss.ss,j));
    	}
    	for(int j=1;j<=m;j++)
    		if(!ban[j])
    			v.pb(mp(edge[j].ss,j));
    	sort(all(v));sort(all(g));
		int p=int(v.size())-1,rec;
    	for(int j=int(g.size())-1;j>=0;j--){
    		rec=0;
    		while(p>=0 and v[p].ff>=g[j].ff)
				merge(edge[v[p].ss].ff),p--;
			for(int k=g[j].ss-1;k>=i;k--){
				int ind=query[k].ss.ff;
				if(query[k].ff==1 and !ban1[ind]){
					if(query[k].ss.ss>=g[j].ff)rec+=merge(edge[ind].ff);
					ban1[ind]=1;st.push(ind);
				}
			}
			for(int k=g[j].ss+1;k<=r;k++){
				int ind=query[k].ss.ff;
				if(query[k].ff==1 and !ban1[ind]){
					if(edge[ind].ss>=g[j].ff)rec+=merge(edge[ind].ff);
					ban1[ind]=1;st.push(ind);	
				}
			}
			ans[g[j].ss]=sz[tap(query[g[j].ss].ss.ff)];
			while(!st.empty())ban1[st.top()]=0,st.pop();
			while(rec--){ //x,y,sz[y]
				int x=history.back().ff.ff;
				int y=history.back().ff.ss;
				int szy=history.back().ss;
				sz[x]-=szy;ata[y]=y;
				history.ppb();	
			}
    	}
    	for(int j=i;j<=r;j++)
    		if(query[j].ff==1)	
				edge[query[j].ss.ff].ss=query[j].ss.ss;	
    }
    for(int i=1;i<=q;i++)
    	if(query[i].ff==2)
    		printf("%d\n",ans[i]);
	return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

bridges.cpp: In function 'int main()':
bridges.cpp:101:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
  101 |     for(int i=1;i<=q;i++)
      |     ^~~
bridges.cpp:104:2: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
  104 |  return 0;
      |  ^~~~~~
bridges.cpp:41:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   41 |     scanf("%d%d",&n,&m);
      |     ~~~~~^~~~~~~~~~~~~~
bridges.cpp:44:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   44 |   scanf("%d%d%d",&u,&v,&w);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~
bridges.cpp:48:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   48 |     scanf("%d",&q);
      |     ~~~~~^~~~~~~~~
bridges.cpp:51:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   51 |   scanf("%d%d%d",&t,&a,&b);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~

• Subtask 1: 13 / 13
• Subtask 2: 16 / 16
• Subtask 3: 17 / 17
• Subtask 4: 0 / 14
• Subtask 5: 13 / 13
• Subtask 6: 0 / 27