oj.uz

Submission #254905

# Submission time Handle Problem Language Result Execution time Memory
254905 2020-07-30T20:09:29 Z Lawliet Bridges (APIO19_bridges) C++17
27 / 100
 3000 ms 30068 KB 
#include <bits/stdc++.h>
 
using namespace std;
typedef pair<int,int> pii;
 
const int MAXN = 100010;
const int MAXT = 200010;
 
int n, m, q;
int raizQ;
int cntWeight;
 
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<pii> sweep[MAXT];
 
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;
}

void compress()
{
	set<int> s;
	map<int,int> conv;

	for(int i = 1 ; i <= m ; i++)
		s.insert( W[i] );

	for(int i = 0 ; i < q ; i++)
		s.insert( queries[i].first );

	for(auto it = s.begin() ; it != s.end() ; it++)
		conv[*it] = ++cntWeight;

	for(int i = 1 ; i <= m ; i++)
		W[i] = conv[ W[i] ];

	for(int i = 0 ; i < q ; i++)
		queries[i].first = conv[ queries[i].first ];
}
 
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 = 1500;
 
	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;
	}

	compress();

	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;
			}
		}

		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[maxW].push_back( { -source , i } );
			}
		}

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

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

		initDSU();

		for(int k = cntWeight ; k > 0 ; k--)
		{
			while( !sweep[k].empty() )
			{
				int type = 0;
				if( sweep[k].back().first < 0 ) type = 1;

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

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

					join( curU , curV );
				}
				if( type == 1 )
				{
					int maxW = k;
					int ind = sweep[k].back().second;
					int source = -sweep[k].back().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();
						}
					}
				}	

				sweep[k].pop_back();
			}
		}
	}
 
	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:92: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:95: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:97:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&q);
  ~~~~~^~~~~~~~~
bridges.cpp:103:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",&type);
   ~~~~~^~~~~~~~~~~~
bridges.cpp:108: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:115: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 4 ms 7424 KB Output is correct
2 Correct 6 ms 7424 KB Output is correct
3 Correct 108 ms 8616 KB Output is correct
4 Correct 25 ms 8576 KB Output is correct
5 Correct 43 ms 8440 KB Output is correct
6 Correct 38 ms 7936 KB Output is correct
7 Correct 40 ms 7680 KB Output is correct
8 Correct 43 ms 8448 KB Output is correct
9 Correct 43 ms 7680 KB Output is correct
10 Correct 43 ms 8448 KB Output is correct
11 Correct 43 ms 8488 KB Output is correct
12 Correct 47 ms 8568 KB Output is correct
13 Correct 54 ms 8448 KB Output is correct
14 Correct 50 ms 8448 KB Output is correct
15 Correct 48 ms 8576 KB Output is correct
16 Correct 40 ms 7680 KB Output is correct
17 Correct 39 ms 7680 KB Output is correct

Subtask #2
0 / 16.0

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

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2918 ms 21736 KB Output is correct
2 Correct 2761 ms 16488 KB Output is correct
3 Execution timed out 3064 ms 19304 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1610 ms 30012 KB Output is correct
2 Correct 270 ms 18284 KB Output is correct
3 Correct 252 ms 19576 KB Output is correct
4 Correct 75 ms 10432 KB Output is correct
5 Correct 428 ms 12528 KB Output is correct
6 Correct 1694 ms 29804 KB Output is correct
7 Correct 414 ms 12524 KB Output is correct
8 Correct 784 ms 24172 KB Output is correct
9 Correct 927 ms 24300 KB Output is correct
10 Correct 643 ms 24180 KB Output is correct
11 Correct 1216 ms 27112 KB Output is correct
12 Correct 1347 ms 27104 KB Output is correct
13 Correct 973 ms 27280 KB Output is correct
14 Correct 400 ms 12520 KB Output is correct
15 Correct 410 ms 12904 KB Output is correct
16 Correct 1592 ms 29932 KB Output is correct
17 Correct 1356 ms 30068 KB Output is correct
18 Correct 1816 ms 29804 KB Output is correct
19 Correct 1322 ms 30012 KB Output is correct
20 Correct 857 ms 27896 KB Output is correct
21 Correct 873 ms 27880 KB Output is correct
22 Correct 1107 ms 29652 KB Output is correct
23 Correct 405 ms 11880 KB Output is correct

Subtask #5
0 / 13.0

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

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7424 KB Output is correct
2 Correct 6 ms 7424 KB Output is correct
3 Correct 108 ms 8616 KB Output is correct
4 Correct 25 ms 8576 KB Output is correct
5 Correct 43 ms 8440 KB Output is correct
6 Correct 38 ms 7936 KB Output is correct
7 Correct 40 ms 7680 KB Output is correct
8 Correct 43 ms 8448 KB Output is correct
9 Correct 43 ms 7680 KB Output is correct
10 Correct 43 ms 8448 KB Output is correct
11 Correct 43 ms 8488 KB Output is correct
12 Correct 47 ms 8568 KB Output is correct
13 Correct 54 ms 8448 KB Output is correct
14 Correct 50 ms 8448 KB Output is correct
15 Correct 48 ms 8576 KB Output is correct
16 Correct 40 ms 7680 KB Output is correct
17 Correct 39 ms 7680 KB Output is correct
18 Execution timed out 3033 ms 23784 KB Time limit exceeded
19 Halted 0 ms 0 KB -