oj.uz

Submission #254895

# Submission time Handle Problem Language Result Execution time Memory
254895 2020-07-30T19:51:22 Z Lawliet Bridges (APIO19_bridges) C++17
46 / 100
 3000 ms 11752 KB 
#include <bits/stdc++.h>
 
using namespace std;
typedef pair<int,int> pii;
 
const int MAXN = 100010;
 
int n, m, q;
int raizQ;
 
int ans[MAXN];
int indInside[MAXN];
int lastWeight[MAXN];
int anc[MAXN], sz[MAXN];
int U[MAXN], V[MAXN], W[MAXN];

bool mark[MAXN];
bool insideBlock[MAXN];
 
vector<int> adj[MAXN];

vector<pii> queries;
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];
}

bool isUpdate(int i)
{
	int val = queries[i].second;
	return ( val > 0 );
}

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

int DFS(int cur)
{
	mark[cur] = true;
	int ans = sz[cur];

	for(int i = 0 ; i < (int)adj[cur].size() ; i++)
		if( !mark[ adj[cur][i] ] ) ans += DFS( adj[cur][i] );

	return ans;
}
 
int main()
{
	scanf("%d %d",&n,&m);
 
	for(int i = 1 ; i <= m ; i++)
		scanf("%d %d %d",&U[i],&V[i],&W[i]);
 
	scanf("%d",&q);
	raizQ = sqrt(q) + 1;
 
	for(int i = 1 ; i <= q ; i++)
	{
		int type;
		scanf("%d",&type);

		if( type == 1 )
		{
			int edge, newW;
			scanf("%d %d",&edge,&newW);

			queries.push_back( { newW , edge } );
		}
		if( type == 2 )
		{
			int s, maxW;
			scanf("%d %d",&s,&maxW);

			queries.push_back( { maxW , -s } );
		}

		ans[i - 1] = -1;
	}

	int lastBlock = (q - 1)/raizQ;

	for(int block = 0 ; block <= lastBlock ; block++)
	{
		//printf("+============================+ Processando bloco %d\n",block);

		int L = block*raizQ;
		int R = (block + 1)*raizQ - 1;
		R = min( R , q - 1 );

		for(int i = 1 ; i <= m ; i++)
		{
			lastWeight[i] = W[i];
			insideBlock[i] = false;
		}

		vector<int> inside;

		for(int i = L ; i <= R ; i++)
		{
			if( isUpdate( i ) ) 
			{
				int edge = queries[i].second;

				if( !insideBlock[edge] )
				{
					indInside[edge] = (int)inside.size();

					//printf(".. edge = %d\n",edge);
					insideBlock[edge] = true;
					inside.push_back( edge );
				}
			}
		}

		for(int i = 0 ; i < L ; i++)
		{
			if( isUpdate( i ) )
			{
				int newW = queries[i].first;
				int edge = queries[i].second;

				lastWeight[edge] = newW;
			}
		}

		sweep.clear();

		for(int i = 1 ; i <= m ; i++)
			if( !insideBlock[i] ) sweep.push_back( { lastWeight[i] , { U[i] , V[i] } } );//, printf("Adicionei %d: %d -> %d com peso %d\n",i,U[i],V[i],lastWeight[i]);

		for(int i = L ; i <= R ; i++)
		{
			if( !isUpdate( i ) )
			{
				int maxW = queries[i].first;
				int source = -queries[i].second;

				//printf("Achei query %d %d\n",source,maxW);

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

		//printf("\n\n\n");
		//printf("------- Sweep Algorithm\n");

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

		initDSU();

		for(int i = 0 ; i < (int)sweep.size() ; i++)
		{
			int type = 0;
			if( sweep[i].second.first < 0 ) type = 1;

			if( type == 0 )//Update
			{
				int curU = sweep[i].second.first;
				int curV = sweep[i].second.second;

				//printf("Juntei %d %d\n",curU,curV);

				join( curU , curV );
			}
			if( type == 1 )
			{
				int maxW = sweep[i].first;
				int ind = sweep[i].second.second;
				int source = -sweep[i].second.first;

				//printf("Respondendo query maxW = %d source = %d ind = %d\n",maxW,source,ind);

				vector<int> weightInside;

				for(int j = 0 ; j < (int)inside.size() ; j++)
					weightInside.push_back( lastWeight[ inside[j] ] );

				for(int j = L ; j <= ind ; j++)
				{
					if( isUpdate( j ) )
					{
						int newW = queries[j].first;
						int edge = queries[j].second;
				
						weightInside[ indInside[edge] ] = newW;
					}
				}

				for(int j = 0 ; j < (int)inside.size() ; j++)
				{
					//printf("...... Tentando colocar %d -> %d com peso %d\n",U[ inside[j] ],V[ inside[j] ],weightInside[j]);
					if( weightInside[j] >= maxW ) 
					{
						int curU = find( U[ inside[j] ] );
						int curV = find( V[ inside[j] ] );

						adj[curU].push_back( curV );
						adj[curV].push_back( curU );
					}
				}

				ans[ind] = DFS( find(source) );
				mark[ find(source) ] = false;

				for(int j = 0 ; j < (int)inside.size() ; j++)
				{
					if( weightInside[j] >= maxW ) 
					{
						int curU = find( U[ inside[j] ] );
						int curV = find( V[ inside[j] ] );

						mark[curU] = mark[curV] = false;

						adj[curU].clear();
						adj[curV].clear();
					}
				}
			}	
		}
	}
 
	for(int i = 0 ; i < q ; i++)
		if( ans[i] != -1 ) printf("%d\n",ans[i]);
}

Compilation message

bridges.cpp: In function 'int main()':
bridges.cpp:69: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:72:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d %d",&U[i],&V[i],&W[i]);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
bridges.cpp:74:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&q);
  ~~~~~^~~~~~~~~
bridges.cpp:80:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",&type);
   ~~~~~^~~~~~~~~~~~
bridges.cpp:85:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d %d",&edge,&newW);
    ~~~~~^~~~~~~~~~~~~~~~~~~~~
bridges.cpp:92:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d %d",&s,&maxW);
    ~~~~~^~~~~~~~~~~~~~~~~~

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2688 KB Output is correct
2 Correct 2 ms 2688 KB Output is correct
3 Correct 32 ms 3200 KB Output is correct
4 Correct 8 ms 3072 KB Output is correct
5 Correct 20 ms 3072 KB Output is correct
6 Correct 18 ms 3072 KB Output is correct
7 Correct 20 ms 3072 KB Output is correct
8 Correct 20 ms 3072 KB Output is correct
9 Correct 24 ms 3072 KB Output is correct
10 Correct 19 ms 3072 KB Output is correct
11 Correct 26 ms 3072 KB Output is correct
12 Correct 20 ms 3072 KB Output is correct
13 Correct 21 ms 3072 KB Output is correct
14 Correct 20 ms 3072 KB Output is correct
15 Correct 22 ms 3072 KB Output is correct
16 Correct 19 ms 3072 KB Output is correct
17 Correct 23 ms 3072 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 2555 ms 10272 KB Output is correct
2 Correct 2597 ms 10212 KB Output is correct
3 Correct 2499 ms 10276 KB Output is correct
4 Correct 2499 ms 10476 KB Output is correct
5 Correct 2539 ms 10136 KB Output is correct
6 Correct 2853 ms 9580 KB Output is correct
7 Correct 2825 ms 9564 KB Output is correct
8 Correct 2801 ms 9596 KB Output is correct
9 Correct 86 ms 5484 KB Output is correct
10 Correct 2436 ms 9048 KB Output is correct
11 Correct 2482 ms 8988 KB Output is correct
12 Correct 2233 ms 9736 KB Output is correct
13 Correct 2526 ms 9464 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1798 ms 8840 KB Output is correct
2 Correct 975 ms 6376 KB Output is correct
3 Correct 1975 ms 8500 KB Output is correct
4 Correct 1816 ms 8812 KB Output is correct
5 Correct 88 ms 5480 KB Output is correct
6 Correct 1887 ms 8676 KB Output is correct
7 Correct 1729 ms 8596 KB Output is correct
8 Correct 1658 ms 8552 KB Output is correct
9 Correct 1470 ms 8564 KB Output is correct
10 Correct 1435 ms 8484 KB Output is correct
11 Correct 1509 ms 8692 KB Output is correct
12 Correct 1434 ms 8804 KB Output is correct

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3066 ms 11752 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 2555 ms 10272 KB Output is correct
2 Correct 2597 ms 10212 KB Output is correct
3 Correct 2499 ms 10276 KB Output is correct
4 Correct 2499 ms 10476 KB Output is correct
5 Correct 2539 ms 10136 KB Output is correct
6 Correct 2853 ms 9580 KB Output is correct
7 Correct 2825 ms 9564 KB Output is correct
8 Correct 2801 ms 9596 KB Output is correct
9 Correct 86 ms 5484 KB Output is correct
10 Correct 2436 ms 9048 KB Output is correct
11 Correct 2482 ms 8988 KB Output is correct
12 Correct 2233 ms 9736 KB Output is correct
13 Correct 2526 ms 9464 KB Output is correct
14 Correct 1798 ms 8840 KB Output is correct
15 Correct 975 ms 6376 KB Output is correct
16 Correct 1975 ms 8500 KB Output is correct
17 Correct 1816 ms 8812 KB Output is correct
18 Correct 88 ms 5480 KB Output is correct
19 Correct 1887 ms 8676 KB Output is correct
20 Correct 1729 ms 8596 KB Output is correct
21 Correct 1658 ms 8552 KB Output is correct
22 Correct 1470 ms 8564 KB Output is correct
23 Correct 1435 ms 8484 KB Output is correct
24 Correct 1509 ms 8692 KB Output is correct
25 Correct 1434 ms 8804 KB Output is correct
26 Correct 2570 ms 10020 KB Output is correct
27 Correct 2770 ms 10176 KB Output is correct
28 Correct 2586 ms 10316 KB Output is correct
29 Correct 2348 ms 10168 KB Output is correct
30 Correct 2775 ms 9988 KB Output is correct
31 Correct 2796 ms 10048 KB Output is correct
32 Execution timed out 3079 ms 9880 KB Time limit exceeded
33 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2688 KB Output is correct
2 Correct 2 ms 2688 KB Output is correct
3 Correct 32 ms 3200 KB Output is correct
4 Correct 8 ms 3072 KB Output is correct
5 Correct 20 ms 3072 KB Output is correct
6 Correct 18 ms 3072 KB Output is correct
7 Correct 20 ms 3072 KB Output is correct
8 Correct 20 ms 3072 KB Output is correct
9 Correct 24 ms 3072 KB Output is correct
10 Correct 19 ms 3072 KB Output is correct
11 Correct 26 ms 3072 KB Output is correct
12 Correct 20 ms 3072 KB Output is correct
13 Correct 21 ms 3072 KB Output is correct
14 Correct 20 ms 3072 KB Output is correct
15 Correct 22 ms 3072 KB Output is correct
16 Correct 19 ms 3072 KB Output is correct
17 Correct 23 ms 3072 KB Output is correct
18 Correct 2555 ms 10272 KB Output is correct
19 Correct 2597 ms 10212 KB Output is correct
20 Correct 2499 ms 10276 KB Output is correct
21 Correct 2499 ms 10476 KB Output is correct
22 Correct 2539 ms 10136 KB Output is correct
23 Correct 2853 ms 9580 KB Output is correct
24 Correct 2825 ms 9564 KB Output is correct
25 Correct 2801 ms 9596 KB Output is correct
26 Correct 86 ms 5484 KB Output is correct
27 Correct 2436 ms 9048 KB Output is correct
28 Correct 2482 ms 8988 KB Output is correct
29 Correct 2233 ms 9736 KB Output is correct
30 Correct 2526 ms 9464 KB Output is correct
31 Correct 1798 ms 8840 KB Output is correct
32 Correct 975 ms 6376 KB Output is correct
33 Correct 1975 ms 8500 KB Output is correct
34 Correct 1816 ms 8812 KB Output is correct
35 Correct 88 ms 5480 KB Output is correct
36 Correct 1887 ms 8676 KB Output is correct
37 Correct 1729 ms 8596 KB Output is correct
38 Correct 1658 ms 8552 KB Output is correct
39 Correct 1470 ms 8564 KB Output is correct
40 Correct 1435 ms 8484 KB Output is correct
41 Correct 1509 ms 8692 KB Output is correct
42 Correct 1434 ms 8804 KB Output is correct
43 Execution timed out 3066 ms 11752 KB Time limit exceeded
44 Halted 0 ms 0 KB -