제출 #1070663

#제출 시각아이디문제언어결과실행 시간메모리
1070663Tozzyyyy다리 (APIO19_bridges)C++17
13 / 100
3071 ms12880 KiB
#pragma GCC optimize("Ofast","unroll-loops")
//#pragma GCC target("arch=skylake")
#include<bits/stdc++.h>
#define all(x) (x).begin() , (x).end()
#define pll pair<long long, long long>
#define pii pair<int , int>
#define fi first
#define se second
#define bit(i,j) ((j >> i) & 1)
using namespace std;

const long long inf = 1e18;
const int MAXN = 1e6+100;
const int mod = 1e9+7;

struct edge{
	int u , v , w;
};
struct query{
	int type , a , b;
};
int ans[MAXN] , par[MAXN] , sz[MAXN];
vector<pair<int & , int>> his;

int find(int x) { return x == par[x] ? x : find(par[x]); }

void join(int a , int b){
	a = find(a) ; 
	b = find(b);
	if(a == b) return ;	
	if(sz[a] < sz[b]) swap(a , b);

	his.push_back({sz[a] , sz[a]});
	his.push_back({par[b] , par[b]});

	par[b] = a;
	sz[a] += sz[b];
}

void roll_back(int until){
	while(his.size() > until){
		his.back().first = his.back().second;
		his.pop_back();
	}
}
int b[MAXN];
int32_t main(){
  	//freopen("B.inp", "r", stdin);
	//freopen("B.out", "w", stdout);
	ios_base::sync_with_stdio(0); cin.tie(0);

	int n , m; cin >> n >> m;
	vector<edge> E(m + 1);
	for(int i = 1 ; i <= m ; i++){
		int x , y , w; cin >> x >> y >> w;
		E[i] = {x , y , w};
	}
	int q; cin >> q;
	vector<query> Q(q+1);
	const int block = 250;
	for(int i = 1 ; i <= q ; i++){
		cin >> Q[i].type >> Q[i].a >> Q[i].b;
	}
	for(int bl = 1 ; bl <= q / block + (q % block != 0) ; bl++){
		vector<int> un_change , change, g;
		vector<query> ask;
		his.clear();
		for(int i = 1 ; i <= n ; i++) sz[i] = 1 , par[i] = i;
		for(int i = (bl - 1) * block + 1 ; i <= min(bl * block , q) ; i++){
			if(Q[i].type == 1) b[Q[i].a] = -1 , change.push_back(i);
			else{
				ask.push_back({i , Q[i].b , Q[i].a});
			}
		}
		for(int i = 1 ; i <= m ; i++){
			if(b[i] == 0) un_change.push_back(i);
			else g.push_back(i);
		}
		sort(all(ask) , [&](query x , query y){
			return x.a > y.a;
		});
		sort(all(un_change) , [&](int x , int y){
			return E[x].w > E[y].w;
		});
		int j = 0;
		for(int i = 0 ; i < ask.size() ; i++){
			while(j < un_change.size() && E[un_change[j]].w >= ask[i].a){
				join(E[un_change[j]].u , E[un_change[j]].v); j++;
			}
			int cnt = his.size();
			
			for(int k = 0; k < change.size() ; k++){
				if(change[k] < ask[i].type){
					b[Q[change[k]].a] = Q[change[k]].b;
				}
			}
			for(int k = 0; k < g.size() ; k++){
				int id = g[k];
				if(b[id] == -1){
					if(E[id].w >= ask[i].a) join(E[id].u , E[id].v);
				}else{
					if(b[id] >= ask[i].a) join(E[id].u , E[id].v);
					b[id] = -1;
				}
			}
			
			ans[ask[i].type] = sz[find(ask[i].b)];
			roll_back(cnt);
		}
		for(int k = 0; k < change.size() ; k++){
			b[change[k]] = 0;
			E[Q[change[k]].a].w = Q[change[k]].b;
		}	
	}
	for(int i = 1 ; i <= q ; i++){
		if(Q[i].type == 2) cout << ans[i] << "\n";
	}


	return 0;
}

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

bridges.cpp: In function 'void roll_back(int)':
bridges.cpp:41:19: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<int&, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   41 |  while(his.size() > until){
      |        ~~~~~~~~~~~^~~~~~~
bridges.cpp: In function 'int32_t main()':
bridges.cpp:86:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<query>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   86 |   for(int i = 0 ; i < ask.size() ; i++){
      |                   ~~^~~~~~~~~~~~
bridges.cpp:87:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   87 |    while(j < un_change.size() && E[un_change[j]].w >= ask[i].a){
      |          ~~^~~~~~~~~~~~~~~~~~
bridges.cpp:92:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   92 |    for(int k = 0; k < change.size() ; k++){
      |                   ~~^~~~~~~~~~~~~~~
bridges.cpp:97:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   97 |    for(int k = 0; k < g.size() ; k++){
      |                   ~~^~~~~~~~~~
bridges.cpp:110:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  110 |   for(int k = 0; k < change.size() ; k++){
      |                  ~~^~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...