Submission #1133879

#	Time	Username	Problem	Language	Result	Execution time	Memory
1133879		benjaminj	다리 (APIO19_bridges)	C++20	100 / 100	2970 ms	7500 KiB

bridges

#include<iostream>
#include<vector>
#include<set>
#include<map>
#include<bitset>
#include<unordered_map>
#include<algorithm>
#include<math.h>
#include<queue>
#include<iomanip>
#include<unordered_set>
using namespace std;


#define ll long long
#define pb push_back	
#define mp make_pair
#define F first
#define S second
#define V vector
#define vi vector<int>
#define vl vector<long long>
#define vb vector<bool>
#define pi pair<int,int>
#define pl pair<long long, long long>
#define setmax(a,b) (a= std::max(a, b))
#define all(i) i.begin(),i.end()
#define REP(i,a,b) for(int i = a; i <= b; i++)
#define PER(i,a,b) for(int i = a; i >= b; i--)
#define sz(i) (int) i.size()


class DisjointSets {
  public:
	vector<int> parents;
	vector<int> sizes;
	DisjointSets(int size) : parents(size), sizes(size, 1) {
		for (int i = 0; i < size; i++) { parents[i] = i; }
	}

	/** @return the "representative" node in x's component */
	int find(int x) { return parents[x] == x ? x : (parents[x] = find(parents[x])); }

	/** @return whether the merge changed connectivity */
	bool unite(int x, int y) {
		int x_root = find(x);
		int y_root = find(y);
		if (x_root == y_root) { return false; }

		if (sizes[x_root] < sizes[y_root]) { swap(x_root, y_root); }
		sizes[x_root] += sizes[y_root];
		parents[y_root] = x_root;
		return true;
	}

	bool connected(int x, int y) { return find(x) == find(y); }
};

struct edge{
	int l;
	int r;
	int w;
	edge(int l, int r, int w) : l(l), r(r), w(w) {}
	bool operator<(const edge& other) const{
		if(w > other.w)return true;
		if(w < other.w)return false;
		return false;
	}
};

int n,m;

V<edge> edges;

V<vi> batch;

bool cmp(const vi &a, const vi &b){
	return a > b;
}

vi found;
int batch_count = 5;
vi found2;
V<vi> adj;

void process_batch(){
	V<edge> unaltered;
	vb modified(m,false);
	V<vi> cars;
	int t = 0;
	V<vi> altered;
	for(auto q : batch){
		if(q[0]==1){
			modified[q[1]]=true;
			altered.pb({t,q[1],q[2]});
		}
		else{
			cars.pb({q[2],q[1],t});
		}
		t++;
	}
	REP(i,0,m-1){
		if(!modified[i]){
			unaltered.pb(edges[i]);
		}
	}
	sort(unaltered.begin(),unaltered.end());
	sort(cars.begin(),cars.end(),cmp);
	sort(altered.begin(),altered.end());
	auto itr = unaltered.begin();
	DisjointSets s(n);
	V<pi> ans;
	for(vi &car : cars){
		batch_count++;
		while(itr!=unaltered.end()&&car[0]<=(*itr).w){
			s.unite((*itr).l,(*itr).r);
			itr++;
		}
		set<int> present;
		for(vi &p : altered){
			if(edges[p[1]].w >= car[0]){
				present.insert(p[1]);
			}
		}
		for(vi p : altered){
			if(p[0]>car[2])break;
			if(p[2] >= car[0]){
				present.insert(p[1]);
			}
			else{
				present.erase(p[1]);
			}
		}
		vi found_components;
		queue<int> components;
		components.push(s.find(car[1]));
		found_components.pb(s.find(car[1]));
		found[s.find(car[1])]=batch_count;
		vi to_delete;
		for(int i : present){
			int l = s.find(edges[i].l);
			int r = s.find(edges[i].r);
			adj[l].pb(r); 
			adj[r].pb(l);
			to_delete.pb(l);
			to_delete.pb(r);
		}
		while(components.size()){
			int c = components.front();
			components.pop();
			for(int u : adj[c]){
				if(found[u]==batch_count)continue;
				found_components.pb(u);
				found[u]=batch_count;
				components.push(u);
			}
		}
		for(int i : to_delete){
			adj[i].clear();
		}
		ll count=0;
		for(int i : found_components){
			count+=s.sizes[i];
		}
		ans.pb({car[2],count});
	}
	sort(ans.begin(),ans.end());
	for(pi p : ans){
		cout << p.S << "\n";
	}
	for(auto q : batch){
		if(q[0]==1){
			edges[q[1]].w=q[2];
		}
	}
	batch.clear();
}

void solve(){
	cin >> n >> m;
	adj = V<vi>(n);
	int x = (ll)sqrt((double)(2.2)*n);
	found = vi(n,0);
	found2 = vi(n+10,0);
	REP(i,0,m-1){
		int x,y,w; cin >> x >> y >> w;
		x--;y--;
		edges.push_back(edge(x,y,w));
	}
	int q; cin >> q;
	while(q--){
		if(batch.size()>=x){
			// cout << "BATCHING " << batch.size() << endl;
			process_batch();
		}
		int a,b,c;
		cin >> a >> b >> c;
		batch.pb({a,b-1,c});
	}
	process_batch();
	cout << endl;
	exit(0);
}

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

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