oj.uz

Submission #254904

# Submission time Handle Problem Language Result Execution time Memory
254904 2020-07-30T20:09:02 Z Lawliet Bridges (APIO19_bridges) C++17
27 / 100
 3000 ms 31316 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 = 1200;
 
	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 5 ms 7424 KB Output is correct
2 Correct 5 ms 7552 KB Output is correct
3 Correct 95 ms 8576 KB Output is correct
4 Correct 24 ms 8576 KB Output is correct
5 Correct 40 ms 8440 KB Output is correct
6 Correct 37 ms 7936 KB Output is correct
7 Correct 37 ms 7680 KB Output is correct
8 Correct 40 ms 8448 KB Output is correct
9 Correct 40 ms 7680 KB Output is correct
10 Correct 42 ms 8448 KB Output is correct
11 Correct 40 ms 8488 KB Output is correct
12 Correct 43 ms 8568 KB Output is correct
13 Correct 50 ms 8448 KB Output is correct
14 Correct 47 ms 8448 KB Output is correct
15 Correct 45 ms 8576 KB Output is correct
16 Correct 35 ms 7728 KB Output is correct
17 Correct 36 ms 7680 KB Output is correct

Subtask #2
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 2880 ms 23660 KB Output is correct
2 Correct 2760 ms 24632 KB Output is correct
3 Correct 2901 ms 24680 KB Output is correct
4 Correct 2723 ms 24748 KB Output is correct
5 Correct 2699 ms 24648 KB Output is correct
6 Execution timed out 3074 ms 22504 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2353 ms 21740 KB Output is correct
2 Correct 2337 ms 16488 KB Output is correct
3 Execution timed out 3076 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 1591 ms 30092 KB Output is correct
2 Correct 255 ms 19052 KB Output is correct
3 Correct 267 ms 20264 KB Output is correct
4 Correct 72 ms 11072 KB Output is correct
5 Correct 457 ms 13200 KB Output is correct
6 Correct 1699 ms 31172 KB Output is correct
7 Correct 468 ms 13160 KB Output is correct
8 Correct 801 ms 24936 KB Output is correct
9 Correct 720 ms 24940 KB Output is correct
10 Correct 644 ms 24940 KB Output is correct
11 Correct 1216 ms 27900 KB Output is correct
12 Correct 1199 ms 27984 KB Output is correct
13 Correct 1078 ms 27884 KB Output is correct
14 Correct 501 ms 13216 KB Output is correct
15 Correct 472 ms 13544 KB Output is correct
16 Correct 1683 ms 31208 KB Output is correct
17 Correct 1628 ms 31316 KB Output is correct
18 Correct 1593 ms 31300 KB Output is correct
19 Correct 1778 ms 31300 KB Output is correct
20 Correct 1142 ms 28656 KB Output is correct
21 Correct 1247 ms 28516 KB Output is correct
22 Correct 1566 ms 30700 KB Output is correct
23 Correct 460 ms 12648 KB Output is correct

Subtask #5
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 2880 ms 23660 KB Output is correct
2 Correct 2760 ms 24632 KB Output is correct
3 Correct 2901 ms 24680 KB Output is correct
4 Correct 2723 ms 24748 KB Output is correct
5 Correct 2699 ms 24648 KB Output is correct
6 Execution timed out 3074 ms 22504 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 7424 KB Output is correct
2 Correct 5 ms 7552 KB Output is correct
3 Correct 95 ms 8576 KB Output is correct
4 Correct 24 ms 8576 KB Output is correct
5 Correct 40 ms 8440 KB Output is correct
6 Correct 37 ms 7936 KB Output is correct
7 Correct 37 ms 7680 KB Output is correct
8 Correct 40 ms 8448 KB Output is correct
9 Correct 40 ms 7680 KB Output is correct
10 Correct 42 ms 8448 KB Output is correct
11 Correct 40 ms 8488 KB Output is correct
12 Correct 43 ms 8568 KB Output is correct
13 Correct 50 ms 8448 KB Output is correct
14 Correct 47 ms 8448 KB Output is correct
15 Correct 45 ms 8576 KB Output is correct
16 Correct 35 ms 7728 KB Output is correct
17 Correct 36 ms 7680 KB Output is correct
18 Correct 2880 ms 23660 KB Output is correct
19 Correct 2760 ms 24632 KB Output is correct
20 Correct 2901 ms 24680 KB Output is correct
21 Correct 2723 ms 24748 KB Output is correct
22 Correct 2699 ms 24648 KB Output is correct
23 Execution timed out 3074 ms 22504 KB Time limit exceeded
24 Halted 0 ms 0 KB -