Submission #123406

#	Time	Username	Problem	Language	Result	Execution time	Memory
123406		figter001	Bridges (APIO19_bridges)	C++17	14 / 100	125 ms	7880 KiB

bridges

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;

const int nax = 1e5 + 100;

int dsu[nax],sz[nax],ans[nax];
int n,m,q;

int find(int u){
	return u == dsu[u] ? u : dsu[u] = find(dsu[u]);
}

int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++){
		dsu[i] = i;
		sz[i] = 1;
	}
	vector<pair<int,pair<int,int>>> e;
	for(int i=0;i<m;i++){
		int u,v,w;
		scanf("%d%d%d",&u,&v,&w);
		e.push_back({w,{u,v}});
		// e.emplace_back(w,u,v);
	}
	scanf("%d",&q);
	for(int i=1;i<=q;i++){
		int t,s,w;
		scanf("%d%d%d",&t,&s,&w);
		e.push_back({w,{-s,-i}});
		// e.emplace_back(w,s,-1);
	}
	sort(e.begin(),e.end());
	reverse(e.begin(),e.end());
	for(int i=0;i<e.size();i++){
		if(e[i].second.second < 0){
			int id = -e[i].second.first;
			int at = -e[i].second.second;
			ans[at] = sz[find(id)];
		}else{
			int u = e[i].second.first;
			int v = e[i].second.second;
			u = find(u);
			v = find(v);
			if(u != v){
				sz[u] += sz[v];
				dsu[v] = u;
			}
		}
	}
	for(int i=1;i<=q;i++){
		printf("%d\n", ans[i]);
	}
}

Compilation message (stderr)

bridges.cpp: In function 'int main()':
bridges.cpp:40:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<e.size();i++){
              ~^~~~~~~~~
bridges.cpp:19:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d",&n,&m);
  ~~~~~^~~~~~~~~~~~~~
bridges.cpp:27:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d%d",&u,&v,&w);
   ~~~~~^~~~~~~~~~~~~~~~~~~
bridges.cpp:31:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&q);
  ~~~~~^~~~~~~~~
bridges.cpp:34:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d%d",&t,&s,&w);
   ~~~~~^~~~~~~~~~~~~~~~~~~

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