제출 #1045034

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1045034		Kel_Mahmut	다리 (APIO19_bridges)	C++14	27 / 100	226 ms	12796 KiB

bridges

#include <bits/stdc++.h>
#define pb push_back
// #define endl ("\n")
#define all(aa) aa.begin(), aa.end()
typedef long long ll;
using namespace std;

struct DSU{
	int n;
	vector<int> par;
	vector<int> sz;
	DSU(int n) : n(n), par(n), sz(n, 1){
		for(int i = 0; i < n; i++) par[i] = i;
	}

	int find(int u){
		if(par[u] == u) return u;
		return par[u] = find(par[u]);
	}

	void merge(int u, int v){
		u = find(u);
		v = find(v);
		if(u == v) return;
		if(sz[v] > sz[u]) swap(u, v);
		par[v] = u;
		sz[u] += sz[v];
	}

	int cnt(int u){
		u = find(u);
		return sz[u];
	}
};

struct SegmentTree{
	int n;
	vector<int> t;
	SegmentTree(int n) : n(n), t(4*n) {}

	void upd(int u, int tl, int tr, int pos, int val){
		if(tl == tr){
			t[u] = val;
			return;
		}
		int tm = (tl + tr) / 2;
		if(pos <= tm)
			upd(u * 2, tl, tm, pos, val);
		else
			upd(u * 2 + 1, tm + 1, tr, pos, val);
		t[u] = min(t[u * 2], t[u * 2 + 1]);
	}

	void upd(int pos, int val){
		upd(1, 0, n - 1, pos, val);
	}

	int query(int u, int tl, int tr, int ql, int qr){
		if(ql <= tl && tr <= qr){
			return t[u];
		}
		int tm = (tl + tr) / 2;
		int ret = INT_MAX;
		if(ql <= tm)
			ret = query(u * 2, tl, tm, ql, qr);
		if(tm < qr)
			ret = min(ret, query(u * 2 + 1, tm + 1, tr, ql, qr));
		return ret;
	}

	int query(int ql, int qr){
		return query(1, 0, n - 1, ql, qr);
	}
};

int main(){
	int n, m;
	cin >> n >> m;
	vector<vector<pair<int, int>>> g(n);
	vector<pair<pair<int, int>, pair<int, int>>> bri(m);
	vector<array<int, 3>> edge;

	bool st2 = 1;
	vector<int> V;
	for(int i = 0; i < m; i++){
		int u, v, c;
		cin >> u >> v >> c;
		u--, v--;
		st2 &= ((u == i) && (v == i + 1));
		V.pb(c);
		g[u].pb(make_pair(v, c));
		g[v].pb(make_pair(u, c));
		bri[i] = make_pair(make_pair(u, g[u].size() - 1), make_pair(v, g[v].size() - 1));
		edge.pb({c, u, v});
	}
	int q; cin >> q;
	if(0 && st2){
		cout <<"CHAIN" << endl;
		SegmentTree st(n - 1);
		for(int i = 0; i < n - 1; i++){
			st.upd(i, V[i]);
		}

		for(int qq = 0; qq < q; qq++){
			int t; cin >> t;
			if(t == 1){
				int ind, val;
				cin >> ind >> val;
				ind--;
				st.upd(ind, val);
			}
			else{
				int u, d;
				cin >> u >> d;
				u--;
				int tl = u, tr = n - 1;
				while(tl < tr){
					int tm = (tl + tr + 1) / 2;
					if(st.query(u, tm - 1) >= d){
						tl = tm;
					}
					else
						tr = tm - 1;
				}
				int upp = tr;
				tl = 0, tr = u;
				while(tl < tr){
					int tm = (tl + tr) / 2;
					if(st.query(tm, u - 1) >= d){
						tr = tm;
					}
					else tl = tm + 1;
				}
				int low = tr;

				cout << upp - low + 1 << endl;
			}
		}
	}
	else if(n <= 1000 && m <= 1000 && q <= 10000){
		int ans = 0;
		vector<int> vis(n);
		function<void(int, int)> dfs = [&](int u, int d){
			vis[u] = 1;
			ans++;
			for(auto [v, c]: g[u]){
				if(d <= c){
					if(!vis[v])
						dfs(v, d);
				}
			}
		};
		for(int i = 0; i < q; i++){
			int t;
			cin >> t;
			if(t == 2){
				int u, d;
				cin >> u >> d;
				u--;
				dfs(u, d);
				cout << ans << endl;
				ans = 0;
				vis.assign(n, 0);
			}
			else{
				int ind, c;
				cin >> ind >> c;
				ind--;
				auto x = bri[ind].first;
				g[x.first][x.second].second = c;
				x = bri[ind].second;
				g[x.first][x.second].second = c;
			}
		}
		exit(0);
	}

	sort(all(edge));
	reverse(all(edge));
	vector<array<int, 3>> Q;
	for(int i = 0; i < q; i++){
		int t;
		cin >> t;
		if(t == 2){
			int u, c;
			cin >> u >> c;
			u--;
			Q.pb({c, u, i});
		}
		else{
			int a, b;
			cin >> a >> b;
		}
	}

	sort(all(Q));
	reverse(all(Q));
	vector<int> ans(Q.size(), -1);
	DSU dsu(n);
	for(int i = 0, j = 0; j < (int) Q.size(); j++){
		while(i < m && edge[i][0] >= Q[j][0]){
			dsu.merge(edge[i][1], edge[i][2]);
			i++;
		}
		ans[Q[j][2]] = dsu.cnt(Q[j][1]);
	}

	for(int i = 0; i < (int) Q.size(); i++){
		cout << ans[i] << endl;
	}
}

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

bridges.cpp: In lambda function:
bridges.cpp:146:13: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  146 |    for(auto [v, c]: g[u]){
      |             ^

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