oj.uz

Submission #254865

# Submission time Handle Problem Language Result Execution time Memory
254865 2020-07-30T18:35:33 Z Lawliet Bridges (APIO19_bridges) C++17
14 / 100
 120 ms 7864 KB 
#include <bits/stdc++.h>

using namespace std;
typedef pair<int,int> pii;

const int MAXN = 50010;
const int MAXQ = 100010;

int n, m, q;

int ans[MAXQ];
int anc[MAXN], sz[MAXN];

vector< pair<int,pii> > sweep;

int find(int cur)
{
	if( anc[cur] == cur ) return cur;
	return anc[cur] = find( anc[cur] );
}
 
void join(int i, int j)
{
	i = find(i); j = find(j);
 
	if( i == j ) return;
 
	if( sz[i] < sz[j] )
		swap( i , j );
 
	anc[j] = i;
	sz[i] += sz[j];
}

int main()
{
	scanf("%d %d",&n,&m);

	for(int i = 1 ; i <= n ; i++)
		sz[i] = 1, anc[i] = i;

	for(int i = 1 ; i <= m ; i++)
	{
		int U, V, W;
		scanf("%d %d %d",&U,&V,&W);

		sweep.push_back( { W , { U , V } } );
	}

	scanf("%d",&q);

	for(int i = 1 ; i <= q ; i++)
	{
		int s, maxW;
		scanf("%*d %d %d",&s,&maxW);

		sweep.push_back( { maxW , { -s , i } } );
	}

	sort( sweep.begin() , sweep.end() );
	reverse( sweep.begin() , sweep.end() );

	for(int i = 0 ; i < (int)sweep.size() ; i++)
	{
		int U = sweep[i].second.first;
		int V = sweep[i].second.second;

		if( U > 0 ) join( U , V );
		else ans[V] = sz[ find(-U) ];
	}

	for(int i = 1 ; i <= q ; i++)
		printf("%d\n",ans[i]);
}

Compilation message

bridges.cpp: In function 'int main()':
bridges.cpp:37: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:45: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:50:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&q);
  ~~~~~^~~~~~~~~
bridges.cpp:55:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%*d %d %d",&s,&maxW);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 13.0

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

Subtask #2
0 / 16.0

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

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 76 ms 3816 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 116 ms 4068 KB Output is correct
2 Correct 54 ms 3560 KB Output is correct
3 Correct 56 ms 3688 KB Output is correct
4 Correct 52 ms 3820 KB Output is correct
5 Correct 103 ms 6372 KB Output is correct
6 Correct 118 ms 7864 KB Output is correct
7 Correct 102 ms 6500 KB Output is correct
8 Correct 90 ms 6508 KB Output is correct
9 Correct 93 ms 6636 KB Output is correct
10 Correct 89 ms 6376 KB Output is correct
11 Correct 102 ms 6752 KB Output is correct
12 Correct 118 ms 6876 KB Output is correct
13 Correct 100 ms 6756 KB Output is correct
14 Correct 103 ms 6500 KB Output is correct
15 Correct 100 ms 6372 KB Output is correct
16 Correct 115 ms 7780 KB Output is correct
17 Correct 117 ms 7652 KB Output is correct
18 Correct 115 ms 7780 KB Output is correct
19 Correct 120 ms 7808 KB Output is correct
20 Correct 106 ms 7136 KB Output is correct
21 Correct 103 ms 7008 KB Output is correct
22 Correct 112 ms 7724 KB Output is correct
23 Correct 89 ms 5988 KB Output is correct

Subtask #5
0 / 13.0

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

Subtask #6
0 / 27.0

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