Submission #172433

#	Time	Username	Problem	Language	Result	Execution time	Memory
172433		dndhk	Bridges (APIO19_bridges)	C++14	13 / 100	66 ms	3948 KiB

bridges

#include <bits/stdc++.h>

#define all(v) (v).begin(), (v).end()
#define sortv(v) sort(all(v))
#define uniqv(v) (v).erase(unique(all(v)), (v).end())
#define pb push_back
#define FI first
#define SE second
#define lb lower_bound
#define ub upper_bound
#define mp make_pair
#define test 1
#define TEST if(test)

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;

const int MOD = 1000000007; // 998244353
const int INF = 2e9;
const ll INFLL = 1e18;
const int MAX_N = 50000;

int N, M, Q;
struct Edge{
	int x, y, z;
	bool operator <(const Edge &a)const{
		return z<a.z;
	}
};
vector<Edge> edge;


struct Group{
	int g[MAX_N+1];
	void ig(){
		for(int i=1; i<=N; i++)	g[i] = i;
	}
	int fg(int x){
		return (x==g[x])?x:g[x] = fg(g[x]);
	}
	void ug(int x, int y){
		x = fg(x); y = fg(y);
		g[x] = y;
	}
} G;

void pro1(){
	for(int i=1; i<=Q; i++){
		int t; scanf("%d", &t);
		int a, b;
		if(t==1){
			scanf("%d%d", &a, &b);
			edge[a].z = b;
		}else{
			scanf("%d%d", &a, &b);
			G.ig();
			for(int j=1; j<=M; j++){
				if(edge[j].z<b)	continue;
				G.ug(edge[j].x, edge[j].y);
			}
			int ans = 0;
			for(int j=1; j<=N; j++){
				if(G.fg(j)==G.fg(a))	ans++;
			}
			printf("%d\n", ans);
		}
	}
}

int main(){
	scanf("%d%d", &N, &M);
	edge.pb({0, 0, 0});
	for(int i=1; i<=M; i++){
		int a, b, c;
		scanf("%d%d%d", &a, &b, &c);
		edge.pb({a, b, c});
	}
	scanf("%d", &Q);
	if(N<=1000 && M<=1000 && Q<=10000){
		pro1();
		return 0;
	}
	return 0;
}

Compilation message (stderr)

bridges.cpp: In function 'void pro1()':
bridges.cpp:53:15: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   int t; scanf("%d", &t);
          ~~~~~^~~~~~~~~~
bridges.cpp:56:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d%d", &a, &b);
    ~~~~~^~~~~~~~~~~~~~~~
bridges.cpp:59:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d%d", &a, &b);
    ~~~~~^~~~~~~~~~~~~~~~
bridges.cpp: In function 'int main()':
bridges.cpp:75: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:79:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d%d", &a, &b, &c);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~
bridges.cpp:82:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &Q);
  ~~~~~^~~~~~~~~~

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