Submission #258025

#	Time	Username	Problem	Language	Result	Execution time	Memory
258025		BamiTorabi	Bridges (APIO19_bridges)	C++14	27 / 100	3084 ms	14468 KiB

bridges

//Sasayego! Sasayego! Shinzou wo Sasageyo!

#include <iostream>
#include <iomanip>
#include <algorithm>
#include <cmath>
#include <ctime>
#include <cstring>
#include <vector>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <numeric>
#include <bitset>
#include <ctime>
#define debug(x)  cerr << #x << " = " << x << endl
#define lid (id << 1)
#define rid (lid ^ 1)
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair <ll, ll> pll;
typedef pair <int, int> pii;

const int maxN = 1e5 + 5;
const int SQ = 1000;
const ll INF = 1e18;
const ll MOD = 1e9 + 7;

pair <int, pii> E[maxN], Q[maxN];
stack <pii> st;
int par[maxN], sz[maxN];
int change[maxN], wt[maxN], ans[maxN];
vector <int> vec, Eix[maxN], Qix[maxN], tmp;

int getpar(int v, bool flag = false){
	if (!flag)
		return (par[v] == v ? v : par[v] = getpar(par[v], flag));
	while (par[v] != v)
		v = par[v];
	return v;
}

void join(int u, int v, bool flag = false){
	u = getpar(u, flag);
	v = getpar(v, flag);
	if (u == v){
		if (flag)
			st.push({-1, -1});
		return;
	}
	if (sz[u] < sz[v])
		swap(u, v);
	if (flag)
		st.push({v, sz[v]});
	par[v] = u;
	sz[u] += sz[v];
	return;
}

void undo(){
	pii pp = st.top(); st.pop();
	if (pp.first == -1)
		return;
	int v = pp.first;
	int u = par[v];
	sz[u] -= pp.second;
	sz[v] = pp.second;
	par[v] = v;
	return;
}

int main(){
	time_t START = clock();
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	int n, m; scanf("%d%d", &n, &m);
	for (int i = 1; i <= m; i++)
		scanf("%d%d%d", &E[i].second.second, &E[i].second.first, &E[i].first);
	int q; scanf("%d", &q);
	for (int i = 0; i < q; i++){
		scanf("%d%d%d", &Q[i].first, &Q[i].second.second, &Q[i].second.first);
		if (Q[i].first == 2)
			vec.push_back(Q[i].second.first);
	}
	sort(vec.begin(), vec.end());
	vec.resize(unique(vec.begin(), vec.end()) - vec.begin());
	for (int i = 1; i <= m; i++)
		E[i].first = upper_bound(vec.begin(), vec.end(), E[i].first) - vec.begin() - 1;
	for (int i = 0; i < q; i++)
		Q[i].second.first = upper_bound(vec.begin(), vec.end(), Q[i].second.first) - vec.begin() - 1;
	for (int id = 0, ss = SQ; id < q; id += ss){
		ss = min(ss, q - id);
		for (int i = 1; i <= m; i++)
			change[i] = false;
		for (int i = 1; i <= n; i++){
			par[i] = i;
			sz[i] = 1;
		}
		for (int i = id; i < id + ss; i++){
			if (Q[i].first == 1)
				change[Q[i].second.second] = true;
			else
				Qix[Q[i].second.first].push_back(i);
		}
		for (int i = 1; i <= m; i++)
			(change[i] ? tmp.push_back(i) : Eix[E[i].first].push_back(i));
		sort(tmp.begin(), tmp.end());
		for (int i = (int)vec.size(); i > -1; i--){
			for (int e : Eix[i])
				join(E[e].second.second, E[e].second.first);
			for (int x : Qix[i]){
				for (int e : tmp)
					wt[e] = E[e].first;
				for (int j = id; j < x; j++)
					if (Q[j].first == 1)
						wt[Q[j].second.second] = Q[j].second.first;
				for (int e : tmp)
					if (wt[e] >= i)
						join(E[e].second.second, E[e].second.first, 1);
				ans[x] = sz[getpar(Q[x].second.second, 1)];
				while (!st.empty())
					undo();
			}
			Eix[i].clear();
			Qix[i].clear();
		}
		for (int i = id; i < id + ss; i++){
			if (Q[i].first == 1)
				E[Q[i].second.second].first = Q[i].second.first;
			else
				printf("%d\n", ans[i]);
		}
	}
	time_t FINISH = clock();
	cerr << "Execution time: " << (ld)(FINISH - START) / CLOCKS_PER_SEC * 1000.0 << " millisecond.seconds.\n";
	return 0;
}
 

Compilation message (stderr)

bridges.cpp: In function 'int main()':
bridges.cpp:78:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  int n, m; scanf("%d%d", &n, &m);
            ~~~~~^~~~~~~~~~~~~~~~
bridges.cpp:80:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d%d", &E[i].second.second, &E[i].second.first, &E[i].first);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
bridges.cpp:81:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  int q; scanf("%d", &q);
         ~~~~~^~~~~~~~~~
bridges.cpp:83:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d%d", &Q[i].first, &Q[i].second.second, &Q[i].second.first);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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