oj.uz

Submission #172447

# Submission time Handle Problem Language Result Execution time Memory
172447 2020-01-01T14:48:43 Z dndhk Bridges (APIO19_bridges) C++14
27 / 100
 136 ms 13440 KB 
#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)	{
				if(a.t==2){
					return idx<a.idx;
				}
				return true;
			}
			if(a.t==2)	return false;
			return idx<a.idx;
		}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, Q+i, 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

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:133: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:137: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:140:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &Q);
  ~~~~~^~~~~~~~~~
bridges.cpp:147: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.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 2 ms 256 KB Output is correct
3 Correct 50 ms 504 KB Output is correct
4 Correct 6 ms 376 KB Output is correct
5 Correct 10 ms 376 KB Output is correct
6 Correct 9 ms 376 KB Output is correct
7 Correct 12 ms 376 KB Output is correct
8 Correct 15 ms 376 KB Output is correct
9 Correct 14 ms 376 KB Output is correct
10 Correct 15 ms 376 KB Output is correct
11 Correct 15 ms 376 KB Output is correct
12 Correct 16 ms 376 KB Output is correct
13 Correct 19 ms 376 KB Output is correct
14 Correct 18 ms 376 KB Output is correct
15 Correct 20 ms 376 KB Output is correct
16 Correct 13 ms 376 KB Output is correct
17 Correct 13 ms 376 KB Output is correct

Subtask #2
0 / 16.0

# Verdict Execution time Memory Grader output
1 Incorrect 58 ms 2672 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 53 ms 2416 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 128 ms 9512 KB Output is correct
2 Correct 59 ms 5352 KB Output is correct
3 Correct 63 ms 5452 KB Output is correct
4 Correct 60 ms 5572 KB Output is correct
5 Correct 113 ms 9444 KB Output is correct
6 Correct 128 ms 9472 KB Output is correct
7 Correct 109 ms 9540 KB Output is correct
8 Correct 97 ms 8928 KB Output is correct
9 Correct 98 ms 8960 KB Output is correct
10 Correct 96 ms 8936 KB Output is correct
11 Correct 113 ms 9156 KB Output is correct
12 Correct 114 ms 9180 KB Output is correct
13 Correct 111 ms 9188 KB Output is correct
14 Correct 106 ms 9424 KB Output is correct
15 Correct 110 ms 11884 KB Output is correct
16 Correct 128 ms 13276 KB Output is correct
17 Correct 136 ms 13260 KB Output is correct
18 Correct 130 ms 13440 KB Output is correct
19 Correct 129 ms 13268 KB Output is correct
20 Correct 116 ms 12540 KB Output is correct
21 Correct 116 ms 12424 KB Output is correct
22 Correct 124 ms 13000 KB Output is correct
23 Correct 103 ms 11364 KB Output is correct

Subtask #5
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 58 ms 2672 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 2 ms 256 KB Output is correct
3 Correct 50 ms 504 KB Output is correct
4 Correct 6 ms 376 KB Output is correct
5 Correct 10 ms 376 KB Output is correct
6 Correct 9 ms 376 KB Output is correct
7 Correct 12 ms 376 KB Output is correct
8 Correct 15 ms 376 KB Output is correct
9 Correct 14 ms 376 KB Output is correct
10 Correct 15 ms 376 KB Output is correct
11 Correct 15 ms 376 KB Output is correct
12 Correct 16 ms 376 KB Output is correct
13 Correct 19 ms 376 KB Output is correct
14 Correct 18 ms 376 KB Output is correct
15 Correct 20 ms 376 KB Output is correct
16 Correct 13 ms 376 KB Output is correct
17 Correct 13 ms 376 KB Output is correct
18 Incorrect 58 ms 2672 KB Output isn't correct
19 Halted 0 ms 0 KB -