Submission #397891

#	Time	Username	Problem	Language	Result	Execution time	Memory
397891		pure_mem	Bridges (APIO19_bridges)	C++14	0 / 100	3079 ms	15604 KiB

bridges

#include <bits/stdc++.h>

#define X first
#define Y second
#define MP make_pair
#define ll long long

using namespace std;

const int MAXN = 1e5 + 12, BS = 300;

struct edge{
	int v, u, w;
}road[MAXN];
struct query{
	int t, v, u;
}need[MAXN];
int n, m, q, dsu[MAXN], sz[MAXN], used[MAXN], ans[MAXN];
stack< pair<int, int> > his;
vector< int > bad[MAXN], good, upd, ask;

int getDsu(int x){
	if(dsu[x] == x)
		return x;
	return getDsu(dsu[x]);
}
void merge(int x, int y){
	x = getDsu(x), y = getDsu(y);
	if(x == y)
		return;
	if(sz[x] > sz[y])
		swap(x, y);
	sz[y] += sz[x], dsu[x] = y;
	his.push(MP(x, y));
}
void init(){
	upd.clear(), good.clear();
	for(int i = 1;i <= n;i++)
		dsu[i] = i, sz[i] = 1;
	for(int i = 1;i <= m;i++)
		used[i] = 0;
	while(!his.empty())
		his.pop();
}

int main () {
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	cin >> n >> m;
	for(int i = 1;i <= m;i++){
		cin >> road[i].v >> road[i].u >> road[i].w;
	}
	cin >> q;
	for(int i = 0;i < q;i++)
		cin >> need[i].t >> need[i].v >> need[i].u; 
	for(int l = 0;l < q;l += BS){
		int r = min(q - 1, l + BS - 1);
		init();
		for(int i = l;i <= r;i++) if(need[i].t == 1) used[need[i].v] = 1;	
		for(int i = 1;i <= m;i++) if(!used[i]) good.push_back(i); else upd.push_back(i);
		for(int i = l;i <= r;i++){
			if(need[i].t == 1){
				road[need[i].v].w = need[i].u;
			}
			else{
				ask.push_back(i);
				for(int j: upd){
					if(road[j].w >= need[i].u)
						bad[i].push_back(j);
				}
			}	
		}
		sort(good.begin(), good.end(), [](int x, int y){return road[x].w > road[y].w;});
		sort(ask.begin(), ask.end(), [](int x, int y){return need[x].u > need[y].u;});
		int ptr = 0;
		for(int i: ask){
			while(ptr < good.size() && road[good[ptr]].w >= need[i].u)
				merge(road[good[ptr]].u, road[good[ptr]].v), ptr++;
			int me = his.size();
			for(int z: bad[i])
				merge(road[z].u, road[z].v);	
			ans[i] = (sz[getDsu(need[i].v)]);
			while(his.size() > me){
				pair<int, int> z = his.top();
				his.pop();
				dsu[z.X] = z.X, sz[z.Y] -= sz[z.X];
			}
		}
	}
	for(int i = 0;i < q;i++)
		if(need[i].t == 2)
			cout << ans[i] << "\n";
}

Compilation message (stderr)

bridges.cpp: In function 'int main()':
bridges.cpp:76:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   76 |    while(ptr < good.size() && road[good[ptr]].w >= need[i].u)
      |          ~~~~^~~~~~~~~~~~~
bridges.cpp:82:21: warning: comparison of integer expressions of different signedness: 'std::stack<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   82 |    while(his.size() > me){
      |          ~~~~~~~~~~~^~~~

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