Submission #1224196

#	Time	Username	Problem	Language	Result	Execution time	Memory
1224196		Bui_Quoc_Cuong	Bridges (APIO19_bridges)	C++20	100 / 100	1943 ms	5716 KiB

bridges

#include<bits/stdc++.h>
using namespace std;
#define FOR(i, a, b) for (int i = (a), _b = (b); i <= _b; i++)
#define FORD(i, a, b) for (int i = (a), _b = (b); i >= _b; i--)
#define fi first
#define se second
#define pb push_back
#define ALL(a) (a).begin(), (a).end()
#define SZ(a) (int)(a.size())
#define BIT(mask, a) ((mask>>(a))&1)
#define MASK(A) (1LL<<(A))
#define ll long long
#define pii pair<int,int>
template <class A,class B> bool maxi(A &a, const B b){if(a < b){a = b; return 1;} return 0;}
template <class A,class B> bool mini(A &a, const B b){if(a > b){a = b; return 1;} return 0;}
const int N = 3e5 + 5, oo = 2e9, MOD = 1e9 + 7;
const ll INF = 1e18;
const int SQRT = 700;
int n, m;
int q;
int mark[N];
int last[N];
int ans[N];
struct Edges
{
	int u,v,w;
}E[N];
struct Queries
{
	int t,u,w;
} Q[N];
int lab[N];
struct Data
{
	int u,lu,v,lv;
}; stack<Data>memo;
int find(int x) 
{
	return lab[x] < 0 ? x : find(lab[x]);
}
bool joint(int u,int v)
{
	int x=find(u),y=find(v);
	if(x==y) return 0;
	if(lab[x]>lab[y])swap(x,y);
	memo.push({x,lab[x],y,lab[y]});
	lab[x]+=lab[y];
	lab[y]=x;
	return 1;
}
int get_ver()
{
	return memo.size();
}
void rollback(int vers)
{
	while(SZ(memo)>vers)
	{
		lab[memo.top().u]=memo.top().lu;
		lab[memo.top().v]=memo.top().lv;
		memo.pop();
	}
}
void process()
{
	cin >> n >> m;
	FOR(i, 1, m)
	{
		int u, v, w; cin >> u >> v >> w;
		E[i] = {u, v, w};
	}    
	cin >> q;	
	FOR(i, 1, q)
	{
		cin >> Q[i].t>>Q[i].u >>Q[i].w;
	}
	FOR(i, 1, n) lab[i] = - 1;
	for(int _t = 1; _t <= q; _t+= SQRT)
	{
		int L = _t, R = min(q, _t + SQRT - 1);
		vector <int> joints, no_joint, qry;		
		FOR(i, L, R)
		{
			if(Q[i].t == 1) mark[Q[i].u] = 1;
			else qry.push_back(i);
		}
		FOR(i, 1, m) 
		{
			if(mark[i]) joints.push_back(i);
			else no_joint.push_back(i);
		}

		sort(ALL(no_joint), [&](int u, int v)
		{
			return E[u].w > E[v].w;
		});
		sort(ALL(qry), [&](int u, int v)
		{
			return Q[u].w > Q[v].w;
		});
		int it = 0;
		for(int id : qry)
		{
			while(it<SZ(no_joint) && E[no_joint[it]].w >= Q[id].w)
			{
				joint(E[no_joint[it]].u,E[no_joint[it]].v);
				it++;
			}
			int vers = get_ver();

			FOR(i,L,id)
			{
				if(Q[i].t==1) last[Q[i].u]=i;
			}

			for(int x : joints)
			{
				if(last[x])
				{
					if(Q[last[x]].w >= Q[id].w)
					{
						joint(E[x].u,E[x].v);
					} 
				} else
				{
					if(E[x].w>=Q[id].w)
					{
						joint(E[x].u,E[x].v);
					}
				}
			}

			ans[id] = abs(lab[find(Q[id].u)]);
			rollback(vers);
			for(int x : joints) last[x] = 0;
		}		

		FOR(i, L, R) if(Q[i].t == 1) E[Q[i].u].w = Q[i].w;
		FOR(i, 1, m) mark[i] = 0;
		rollback(0);
	}

	FOR(i,1,q) if(Q[i].t==2) cout << ans[i] << "\n";
}	
signed main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(nullptr); cout.tie(nullptr);
    #define taskname "kieuoanh"
    if(fopen(taskname".inp", "r"))
    {
        freopen(taskname".inp", "r", stdin);
        freopen(taskname".out", "w", stdout);
    }
    int tc = 1; 
    //cin >> tc;
    while(tc--) process();
    return 0;
}

Compilation message (stderr)

bridges.cpp: In function 'int main()':
bridges.cpp:152:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  152 |         freopen(taskname".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
bridges.cpp:153:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  153 |         freopen(taskname".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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