제출 #1275092

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1275092		nthvn	다리 (APIO19_bridges)	C++20	100 / 100	1422 ms	10184 KiB

bridges

#include "bits/stdc++.h"
using namespace std;

#define LOG(n) (63 - __builtin_clzll((n)))
#define fi first
#define se second
#define pii pair<int,int> 
#define all(x) x.begin(), x.end()
#define sz(x) (int)x.size()
#define pb push_back
#define ll long long
const int N=  1e5+5;
const int B = 1000;
int n,m,q;
struct Edge{
	int u,v,w; 
}e[N];
int t[N],x[N],y[N];
vector<int> to_join[B+5],ask, unchanged, upd;
bool changed[N];
int fans[N];

struct DSU{
	int p[N],sze[N];
	vector<pair<int &, int>> history;
	void reset(){
		for(int i=1;i<=n;i++) p[i]=i, sze[i]=1;
		history.clear();
	}
	int get(int a){
		return (p[a]==a)? a: get(p[a]);
	}
	void unite(int a, int b){
		a= get(a), b= get(b);
		if(a==b) return;
		
		if(sze[a]< sze[b]) swap(a,b);
		history.pb({sze[a],sze[a]});
		history.pb({p[b], p[b]});
		p[b]=a;
		sze[a]+=sze[b];
	}
	int snapshot() {return sz(history);}
	
	void rollback(int until){
		while(snapshot()> until){
			history.back().fi  = history.back().se;
			history.pop_back();
		}
	}
}dsu;


signed main(){
	ios_base::sync_with_stdio(NULL);
	cin.tie(NULL);
	if(fopen("TASK.INP", "r")){
		freopen("TASK.INP", "r", stdin);
		freopen("TASK.OUT", "w", stdout);
	}
	cin>>n>>m;
	for(int i=1;i<=m;i++) {
		int u,v,w; cin>>u>>v>>w;
		e[i]={u,v,w};
	}
	cin>>q;
	for(int l=1; l<=q; l+=B){
		for(int i =l;i<l+B;i++) cin>>t[i]>>x[i]>>y[i];
		
		dsu.reset();
		ask.clear(), unchanged.clear(), upd.clear();
		memset(changed,0,sizeof(changed));
		
		for(int i=l;i<l+B;i++){
			if(t[i]==1){
				changed[x[i]]= true;
				upd.pb(i);
			}
			else ask.pb(i);
		}
		for(int i=1;i<=m;i++) if(!changed[i]) unchanged.pb(i);
		for(int i=l;i<l+B;i++){
			if(t[i]==1) e[x[i]].w= y[i];
			else{
				for(auto &j: upd){
					if(e[x[j]].w>=y[i]) to_join[i-l].pb(x[j]);
				}
			}
		}
		sort(all(ask), [&](int &i, int &j){
			return y[i]<y[j];
		});
		sort(all(unchanged), [&](int &i ,int &j){
			return e[i].w< e[j].w;
		});
		while(sz(ask)){
			int id = ask.back();
			ask.pop_back();
			while(sz(unchanged)&&y[id]<=e[unchanged.back()].w){
				int i = unchanged.back();
				unchanged.pop_back();
				dsu.unite(e[i].u, e[i].v);
			}
			int ckp = dsu.snapshot();
			while(sz(to_join[id-l])) {
				int i = to_join[id-l].back();
				to_join[id-l].pop_back();
				dsu.unite(e[i].u, e[i].v);
			}
			x[id] = dsu.get(x[id]);
			fans[id] = dsu.sze[x[id]];
			dsu.rollback(ckp);
		}
		
		
	}
	for(int i=1;i<=q;i++) {
		if(t[i]==2)cout<<fans[i]<<"\n";
	}
}

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

bridges.cpp: In function 'int main()':
bridges.cpp:58:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   58 |                 freopen("TASK.INP", "r", stdin);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
bridges.cpp:59:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   59 |                 freopen("TASK.OUT", "w", stdout);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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