Submission #172445

#	Time	Username	Problem	Language	Result	Execution time	Memory
172445		dndhk	Bridges (APIO19_bridges)	C++14	13 / 100	3100 ms	10124 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 = 50010;
const int MAX_Q = 100010;

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

struct Group{
	int g[MAX_N+1];
	int sz[MAX_N+1];
	void ig(){
		for(int i=1; i<=N; i++)	{
			g[i] = i;
			sz[i] = 1;
		}
	}
	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);
		if(x==y)	return;
		if(sz[x]>sz[y]){
			g[y] = x;
			sz[x]+=sz[y];
		}else{
			g[x] = y;
			sz[y]+=sz[x];
		}
	}
} 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);
		}
	}
}

struct ST{
	int t, idx, x, y, z;
	bool operator <(const ST &a)const{
		if(z==a.z){
			if(t==2)	return true;
			return false;
		}return z<a.z;
	}
};
vector<ST> vt;

int ans[MAX_Q+1];

void pro2(){
	G.ig();
	for(int i=1; i<=M; i++){
		vt.pb({1, 0, edge[i].x, edge[i].y, edge[i].z});
	}
	for(int i=0; i<Q; i++){
		vt.pb({2, i, query[i].x, 0, query[i].y});
	}
	sort(vt.begin(), vt.end());
	while(!vt.empty()){
		ST now = vt.back(); vt.pop_back();
		if(now.t==1){
			G.ug(now.x, now.y);
		}else{
			ans[now.idx] = G.sz[G.fg(now.x)];
		}
	}
	for(int i=0; i<Q; i++){
		printf("%d\n", ans[i]);
	}
}


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;
	}
	bool tf = true;
	for(int i=1; i<=Q; i++){
		int a, b, c; scanf("%d%d%d", &a, &b, &c);
		if(a==1)	tf = false;
		query.pb({a, b, c});
	}
	if(tf){
		pro2();
		return 0;
	}
	return 0;
}

Compilation message (stderr)

bridges.cpp: In function 'void pro1()':
bridges.cpp:69: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:72: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:75: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:127: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:131: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:134:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &Q);
  ~~~~~^~~~~~~~~~
bridges.cpp:141:21: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   int a, b, c; scanf("%d%d%d", &a, &b, &c);
                ~~~~~^~~~~~~~~~~~~~~~~~~~~~

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