제출 #1120690

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1120690		Thunnus	다리 (APIO19_bridges)	C++17	100 / 100	1624 ms	32244 KiB

bridges

/*
#include<bits/stdc++.h>
using namespace std;
using i64 = long long;
#define int i64
#define vi vector<int>
#define vvi vector<vi>
#define pii pair<int, int>
#define fi first
#define se second
#define sz(x) (int)(x).size()

const int SZ = 1e3;

struct DSU{
    vi par, size_;
    stack<int> rec;
    DSU(int n) : par(n), size_(n, 1){
        iota(par.begin(), par.end(), 0);
    }

    inline void reset(){
        fill(size_.begin(), size_.end(), 1);
        iota(par.begin(), par.end(), 0);
        return;
    }

    inline int find_set(int a){
        while(a != par[a]){
            a = par[a];
        }
        return a;
    }

    inline bool unite(int a, int b){
        a = find_set(a), b = find_set(b);
        if(a == b) return false;
        if(size_[a] < size_[b]) swap(a, b);
        rec.emplace(b);
        size_[a] += size_[b];
        par[b] = par[a];
        return true; 
    }

    inline void rollback(int mb){
        while(sz(rec) > mb){
            int lst = rec.top();
            rec.pop();
            size_[par[lst]] -= size_[lst];
            par[lst] = lst;
        }
        return;
    }
};

signed main(){
    ios_base::sync_with_stdio(false); cin.tie(0);
    int n, m, q;
    cin >> n >> m;
    vector<array<int, 3>> bridges(m);
    for(int i = 0; i < m; i++){
        cin >> bridges[i][0] >> bridges[i][1] >> bridges[i][2];
        bridges[i][0]--, bridges[i][1]--;
    }
    cin >> q;
    vi ans(q);
    vector<array<int, 3>> queries(q);
    for(int i = 0; i < q; i++){
        cin >> queries[i][0] >> queries[i][1] >> queries[i][2];
        queries[i][1]--;
    }

    vvi join2(SZ + 1);
    for(int i = 0; i < q; i += SZ){
        int till = min(q, i + SZ);
        vi upd, ask, unchanged;
        vb changed(m);
        DSU dsu(n);
        for(int j = i; j < till; j++){
            if(queries[j][0] == 1){
                changed[queries[j][1]] = true;
                upd.emplace_back(j);
            }
            else{
                ask.emplace_back(j);
            }
        }
        for(int j = 0; j < m; j++){
            if(!changed[j]){
                unchanged.emplace_back(j);
            }
        }

        for(int j = i; j < till; j++){
            if(queries[j][0] == 1){
                bridges[queries[j][1]] = queries[j][2];
            }
            else{
                join2[j - i].clear();
                for(int &u : upd){
                    if(bridges[u][2] >= queries[j][2]){
                        join2[j - i].emplace_back(queries[u][1]);
                    }
                }
            }
        }

        sort(ask.begin(), ask.end(), [&](const int a, const int b){return queries[a][2] > queries[b][2];} );
        sort(unchanged.begin(), unchanged.end(), [&](const int a, const int b){return bridges[a][2] > bridges[b][2];} );

        int idx = 0;
        for(int &x : ask){
            while(idx < sz(unchanged) && bridges[unchanged[idx]][2] >= x){
                dsu.unite(bridges[unchanged[idx]][0], bridges[unchanged[idx]][1]);
                idx++;
            }
            int temp = sz(dsu.rec);
            for(int &jo : join2[x - l]){
                dsu.unite(bridges[jo][0], bridges[jo][1]);
            }
            ans[x] = sz(dsu.size_[dsu.find_set(queries[x][1])]);
            dsu.rollback(temp);
        }
    }

    for(int i = 0; i < q; i++){
        if(queries[i][0] == 2){
            cout << ans[i] << "\n";
        }
    }
    return 0;
}
*/
#include <bits/stdc++.h>
#define FOR(i, x, y) for (int i = x; i < y; i++)
typedef long long ll;
using namespace std;

const int B = 1000;

int n, m, q;

stack<int> stck;
int sz[100001], cmp[100001];

void reset() {
	iota(cmp + 1, cmp + 1 + n, 1);
	fill(sz + 1, sz + n + 1, 1);
}

inline int find(int a) {
	while (cmp[a] != a) a = cmp[a];
	return a;
}

void onion(int a, int b) {
	a = find(a), b = find(b);
	if (a == b) return;
	if (sz[a] > sz[b]) swap(a, b);
	stck.push(a);
	sz[b] += sz[a];
	cmp[a] = cmp[b];
}

void rollback(int x) {
	while (stck.size() > x) {
		int k = stck.top();
		stck.pop();
		sz[cmp[k]] -= sz[k];
		cmp[k] = k;
	}
}

int u[100001], v[100001], w[100001];
int t[100001], x[100001], y[100001];
bool changed[100001];
vector<int> to_join[B];
int ans[100001];

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cin >> n >> m;
	FOR(i, 1, m + 1) cin >> u[i] >> v[i] >> w[i];
	cin >> q;
	FOR(i, 1, q + 1) cin >> t[i] >> x[i] >> y[i];

	for (int l = 1; l <= q; l += B) {
		int r = min(q + 1, l + B);
		reset();
		fill(changed + 1, changed + m + 1, false);

		vector<int> ask, upd, unchanged;
		FOR(i, l, r) {
			if (t[i] == 1) {
				changed[x[i]] = true;
				upd.push_back(i);
			} else ask.push_back(i);
		}
		FOR(i, 1, m + 1) if (!changed[i]) unchanged.push_back(i);

		FOR(i, l, r) {
			if (t[i] == 1) w[x[i]] = y[i];
			else {
				to_join[i - l].clear();
				for (int j : upd)
					if (w[x[j]] >= y[i]) to_join[i - l].push_back(x[j]);
			}
		}

		sort(ask.begin(), ask.end(), [&](int a, int b) { return y[a] > y[b]; });
		sort(unchanged.begin(), unchanged.end(),
		     [&](int a, int b) { return w[a] > w[b]; });

		int ptr = 0;
		for (int i : ask) {
			while (ptr < unchanged.size() && w[unchanged[ptr]] >= y[i]) {
				onion(u[unchanged[ptr]], v[unchanged[ptr]]);
				ptr++;
			}
			int prev_size = stck.size();
			for (int j : to_join[i - l]) onion(u[j], v[j]);
			ans[i] = sz[find(x[i])];
			rollback(prev_size);
		}
	}

	FOR(i, 1, q + 1) if (t[i] == 2) cout << ans[i] << '\n';
}

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

bridges.cpp: In function 'void rollback(int)':
bridges.cpp:166:21: warning: comparison of integer expressions of different signedness: 'std::stack<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  166 |  while (stck.size() > x) {
      |         ~~~~~~~~~~~~^~~
bridges.cpp: In function 'int main()':
bridges.cpp:217:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  217 |    while (ptr < unchanged.size() && w[unchanged[ptr]] >= y[i]) {
      |           ~~~~^~~~~~~~~~~~~~~~~~

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