Submission #231204

#	Time	Username	Problem	Language	Result	Execution time	Memory
231204		ChrisT	Bridges (APIO19_bridges)	C++17	100 / 100	2327 ms	8768 KiB

bridges

#include <bits/stdc++.h>
using namespace std;
using pii = pair<int,int>;
using pib = pair<int,bool>;
using ll = long long;
using pll = pair<ll,ll>;
using ld = long double;
#define all(x) (x).begin(),(x).end()
#ifdef fread_unlocked
#define fread fread_unlocked
#define fwrite fwrite_unlocked
#endif
#define lc ind<<1
#define rc ind<<1|1
const int MN = 1e5+4, MOD = 1e9+7, BASE = 31, SQRT = 700;
int p[MN],sz[MN],st[MN],sp;
int find (int n) {return p[n] == n ? n : find(p[n]);}
void merge (int a, int b) {
	if ((a=find(a))==(b=find(b))) {st[++sp]=0;return;}
	if (sz[a] > sz[b]) swap(a,b);
	sz[p[st[++sp]=a]=b] += sz[a];
}
void undo () {
	int a = st[sp--];
	if (a) {
		sz[p[a]] -= sz[a];
		p[a] = a;
	}
}
void reset(int n) {iota(p+1,p+n+1,1);fill(sz+1,sz+n+1,1);sp=0;}
struct Edge {
	int a,b,w,ind;
	void read(int _i) {ind=_i;scanf("%d%d%d",&a,&b,&w);}
} edges[MN], temp[MN];
struct Thing {
	int a,b,t;
} upd[SQRT+5], query[SQRT+5];
bool seen[MN];
int main () {
	int n,m;
	scanf ("%d %d",&n,&m);
	for (int i = 1; i <= m; i++) edges[i].read(i);
	int q; scanf ("%d",&q);
	for (int qind = 0; qind < q; qind+=SQRT) {
		reset(n);
		int ed = min(q,qind+SQRT),qi=0,ui=0; vector<int> change;
		for (int i = qind; i < ed; i++) {
			int t,a,b;
			scanf ("%d %d %d",&t,&a,&b);
			if (t == 1) upd[ui++]={a,b,i}, change.push_back(a);
			else query[qi++]={a,b,i};
		}
		sort(all(change)); change.erase(unique(all(change)),change.end()); int ree = change.size(), ti = 0;
		int _pp = 0;
		for (int i = 1; i <= m; i++) {
			if (_pp<ree&&change[_pp]==i)_pp++;
			else temp[ti++] = edges[i];
		}
		sort(temp,temp+ti,[&](const Edge &a, const Edge &b){return a.w<b.w;});
		sort(query,query+qi,[&](const Thing &a, const Thing &b){return a.b>b.b;});
		--ti;
		for (int qq = 0; qq < qi; qq++) {
			Thing &cur = query[qq];
			while (~ti && temp[ti].w >= cur.b) {
				merge(temp[ti].a,temp[ti].b);
				--ti;
			}
			int cnt = 0;
			for (int j=ui-1;~j;j--) if(upd[j].t<=cur.t&&!seen[upd[j].a]){
				Thing &u = upd[j];
				seen[u.a]=1;
				if (u.b >= cur.b) ++cnt, merge(edges[u.a].a,edges[u.a].b);
			}
			for (int i : change) if (!seen[i]&&edges[i].w>=cur.b){
				++cnt;
				merge(edges[i].a,edges[i].b);
			}
			cur.a = sz[find(cur.a)];
			while (cnt--) undo();
			for (int i : change) seen[i]=0;
		}
		sort(query,query+qi,[&](const Thing &a, const Thing &b){return a.t<b.t;});
		for (int i = 0; i < qi; i++) printf ("%d\n",query[i].a);
		for (int i = 0; i < ui; i++) {
			Thing &u = upd[i];
			edges[u.a].w = u.b;
		}
	}
	return 0;
}

Compilation message (stderr)

bridges.cpp: In function 'int main()':
bridges.cpp:41:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf ("%d %d",&n,&m);
  ~~~~~~^~~~~~~~~~~~~~~
bridges.cpp:43:15: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  int q; scanf ("%d",&q);
         ~~~~~~^~~~~~~~~
bridges.cpp:49:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf ("%d %d %d",&t,&a,&b);
    ~~~~~~^~~~~~~~~~~~~~~~~~~~~
bridges.cpp: In member function 'void Edge::read(int)':
bridges.cpp:33:33: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  void read(int _i) {ind=_i;scanf("%d%d%d",&a,&b,&w);}
                            ~~~~~^~~~~~~~~~~~~~~~~~~

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