oj.uz

답안 #123406

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
123406 2019-07-01T11:53:12 Z figter001 다리 (APIO19_bridges) C++17
14 / 100
 125 ms 7880 KB 
#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

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.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 376 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 85 ms 6732 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 76 ms 6124 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 121 ms 7836 KB Output is correct
2 Correct 52 ms 3564 KB Output is correct
3 Correct 64 ms 3688 KB Output is correct
4 Correct 56 ms 3808 KB Output is correct
5 Correct 105 ms 6372 KB Output is correct
6 Correct 122 ms 7780 KB Output is correct
7 Correct 104 ms 6372 KB Output is correct
8 Correct 86 ms 6504 KB Output is correct
9 Correct 87 ms 6636 KB Output is correct
10 Correct 86 ms 6380 KB Output is correct
11 Correct 103 ms 6856 KB Output is correct
12 Correct 103 ms 6884 KB Output is correct
13 Correct 99 ms 6760 KB Output is correct
14 Correct 107 ms 6500 KB Output is correct
15 Correct 106 ms 6452 KB Output is correct
16 Correct 125 ms 7800 KB Output is correct
17 Correct 125 ms 7780 KB Output is correct
18 Correct 120 ms 7880 KB Output is correct
19 Correct 119 ms 7780 KB Output is correct
20 Correct 107 ms 7116 KB Output is correct
21 Correct 105 ms 7136 KB Output is correct
22 Correct 115 ms 7780 KB Output is correct
23 Correct 96 ms 6116 KB Output is correct

Subtask #5
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 85 ms 6732 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 376 KB Output isn't correct
2 Halted 0 ms 0 KB -