제출 #383088

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
383088		Tekor	Bridges (APIO19_bridges)	C++17	100 / 100	2577 ms	6060 KiB

bridges

#include <bits/stdc++.h>
using namespace std;
#define f first
#define s second
#define ll long long
#define ld long double
#define pii pair <int,int>
#define pll pair <ll,ll>
#define pil pair <int,ll>
#define pli pair <ll,int>
#define pss pair <short,short>
#define ull unsigned long long
#define pdd pair <ld,ld> 
#define pb push_back
#define mp make_pair
#define puu pair<ull,ull>
#define pvv pair<vector<int>, vector<int> >
#define _bp __builtin_popcount
#define ptt pair <pnode,pnode>
#define all(v) v.begin(),v.end()
#define en "\n"
void file()
{
    freopen("input.txt","r",stdin);
    freopen("f.txt","w",stdout);
}
void boos()
{
	ios_base :: sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
}
//const long double pi = acos(-1);
const ll INF = (ll)1e9 + 7ll;
const ll INF1 = 998244353;
const ll INF2 = (ll)1e9 + 9ll;
const ll LLINF = (ll)1e18;
const ll INTmx = (ll)1e9;
const ld EPS = (ld)1e-15;
const int N = 1e5 + 100;
const int bl = 830;
int dsu[N],sz[N],last[N],ans[N],val[N],n,m;
bool ban[N],tt[N];
pair <pii,pii> reb[N];
pair <pii,pii> reb1[N];
vector <pair<pii,pii> > dob;
vector <pair <int,pii> > zap;
bool cmp(pair <pii,pii> x,pair <pii,pii> y)
{
	return x.f.f > y.f.f;
}
bool cmp1(pair <int,pii> x,pair <int,pii> y)
{
	return x.f > y.f;
}
int getroot(int v)
{
	return dsu[v] == v ? v : dsu[v] = getroot(dsu[v]);
}
int getroot1(int v)
{
	return dsu[v] == v ? v : getroot1(dsu[v]);
}
void merg(int v,int u)
{
	v = getroot(v);
	u = getroot(u);
	if(v == u)return;
	if(sz[v] >= sz[u])
	{
		dsu[u] = v;
		sz[v] += sz[u];
	}else {
		dsu[v] = u;
		sz[u] += sz[v];
	}
}
vector <pair <int,pii> > calb;
void merg1(int v,int u)
{
	v = getroot1(v);
	u = getroot1(u);
	if(v == u)return;
	calb.pb(mp(u,mp(u,sz[u])));
	calb.pb(mp(v,mp(v,sz[v])));
	if(sz[v] >= sz[u])
	{
		dsu[u] = v;
		sz[v] += sz[u];
	}else {
		dsu[v] = u;
		sz[u] += sz[v];
	}
}
void fin(int s,int w,int num)
{
	for(int i = 0;i < dob.size();i++)
	{
		if(w <= dob[i].s.s && dob[i].f.f <= num && dob[i].f.s >= num)
		{
			merg1(reb1[dob[i].s.f].s.f,reb1[dob[i].s.f].s.s);
		}
	}
	ans[num] = sz[getroot1(s)];
	while(!calb.empty())
	{
		dsu[calb.back().f] = calb.back().s.f;
		sz[calb.back().f] = calb.back().s.s;
		calb.pop_back();
	}
}
int main()
{
	boos();
	//file();
	cin >> n >> m;
	for(int i = 1;i <= m;i++)
	{
		cin >> reb[i].s.f >> reb[i].s.s >> reb[i].f.f;
		reb[i].f.s = i;
		reb1[i] = reb[i];
		last[i] = 1;
		val[i] = reb[i].f.f;
	}
	sort(reb + 1,reb + m + 1,cmp);
	int q;
	cin >> q;
	for(int t = 1;t <= q;t++)
	{
		int typ;
		cin >> typ;
		if(typ == 1)
		{
			int num,x;
			cin >> num >> x;
			ban[num] = 1;
			if(last[num] < t)dob.pb(mp(mp(last[num],t - 1),mp(num,val[num])));
			last[num] = t;
			val[num] = x;
		}else {
			int s,w;
			cin >> s >> w;
			tt[t] = 1;
			zap.pb(mp(w,mp(s,t)));
		}
		if(t % bl && t != q)continue;
		sort(all(zap),cmp1);
		int R = 0;
		for(int i = 1;i <= m;i++)
		{
			if(ban[i])
			{
				dob.pb(mp(mp(last[i],t),mp(i,val[i])));
			}
		}
		for(int i = 1;i <= n;i++)
		{
			dsu[i] = i;
			sz[i] = 1;
		}
		for(int i = 1;i <= m;i++)
		{
			while(R < zap.size() && zap[R].f > reb[i].f.f)
			{
				fin(zap[R].s.f,zap[R].f,zap[R].s.s);
				R++;
			}
			if(ban[reb[i].f.s])continue;
			merg(reb[i].s.f,reb[i].s.s);
		}
		while(R < zap.size())
		{
			fin(zap[R].s.f,zap[R].f,zap[R].s.s);
			R++;
		}
		zap.clear();
		for(int i = 0;i < dob.size();i++)
		{
			reb1[dob[i].s.f].f.f = dob[i].s.s;
		}
		dob.clear();
		for(int i = 1;i <= m;i++)
		{
			ban[i] = 0;
			last[i] = t + 1;
			reb[i] = reb1[i];
		}
		sort(reb + 1,reb + m + 1,cmp);
	}
	for(int i = 1;i <= q;i++)
	{
		if(tt[i])
		{
			cout << ans[i] << en;
		}
	}
}

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

bridges.cpp: In function 'void fin(int, int, int)':
bridges.cpp:97:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<std::pair<int, int>, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   97 |  for(int i = 0;i < dob.size();i++)
      |                ~~^~~~~~~~~~~~
bridges.cpp: In function 'int main()':
bridges.cpp:163:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  163 |    while(R < zap.size() && zap[R].f > reb[i].f.f)
      |          ~~^~~~~~~~~~~~
bridges.cpp:171:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  171 |   while(R < zap.size())
      |         ~~^~~~~~~~~~~~
bridges.cpp:177:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<std::pair<int, int>, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  177 |   for(int i = 0;i < dob.size();i++)
      |                 ~~^~~~~~~~~~~~
bridges.cpp: In function 'void file()':
bridges.cpp:24:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   24 |     freopen("input.txt","r",stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
bridges.cpp:25:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   25 |     freopen("f.txt","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