oj.uz

Submission #314854

# Submission time Handle Problem Language Result Execution time Memory
314854 2020-10-21T13:45:17 Z CaroLinda Bridges (APIO19_bridges) C++14
100 / 100
 2625 ms 17276 KB 
#include <bits/stdc++.h>

#define all(x) x.begin(),x.end()
#define ll long long
#define sz(x) (int)(x.size())

const int MAXN = 5e4+10 ;
const int MAXQ = 1e5+10 ;
const int MAXM = 1e5+10 ;
const int perfectQ = 800 ;

//NAO ESQUECE DE MUDAR O PERFECTQ PELO AMOR DE DEUS

using namespace std ;

struct Edge
{

	int u , v , weight , tin, tout ;

	Edge(int u=0, int v=0, int weight=0, int tin=0, int tout=0) :
	u(u) , v(v) , weight(weight), tin(tin), tout(tout) {}

	bool operator < ( Edge other ) const { return weight > other.weight ; }

} ;

int N , M , Q , cnt ;
int U[MAXM], V[MAXM] , W[MAXM ] ;
int lastChanged[MAXM] , ansQuery[MAXQ] ;
vector<int> adj[MAXN] ;
vector<Edge> edge ;
vector< tuple<int,int,int> > queries ;
bool vis[MAXN] ;

//dsu stuff
int pai[MAXN] ;
int componentSize[MAXN] ;

int find(int x)
{
	if(x == pai[x] ) return x ;
	return pai[x] = find(pai[x]); 
}

void join(int x, int y)
{
	x = find(x) ;
	y= find(y) ;

	if(x == y) return ;

	if(componentSize[x] > componentSize[y])
		swap(x,y) ;

	componentSize[y] += componentSize[x] ;
	pai[x] = y ;

}

void dfs(int x)
{
	vis[x] =true; 
	cnt += componentSize[x] ;

	for(auto e : adj[x])
		if(!vis[e]) dfs(e) ;
}

char c ;
void read(int &num)
{
	num = 0 ;

	c = getchar() ;

	for(; ( c > 47 && c < 58) ; c = getchar() ) 
		num = num*10 + (c - '0') ;

}

int main()
{
	read(N) , read(M) ;
	for(int i = 1 ; i <= M ; i++ )
	{
		read( U[i] ) ;
		read(V[i] ) ;
		read(W[i]) ;
	}

	read(Q) ;

	for(int i = 1 ,t , x , y ; i <= Q ; i++ )
	{

		read(t) , read(x) , read(y) ;

		if(t == 1)
		{
			edge.push_back(Edge( U[x] , V[x] , W[x] , lastChanged[x] , i-1 ) );
			lastChanged[x] = i ;
			W[x] = y ;
		}
		else queries.push_back( make_tuple( y , x , i ) ) ;

	}

	for(int i = 1 ; i <= M ; i++ ) 
		edge.push_back( Edge( U[i] , V[i] , W[i] , lastChanged[i] , Q+1 ) ) ;

	sort(all(edge)) ;
	sort(all(queries), [&](tuple<int,int,int> x, tuple<int,int,int> y) { return get<0>(x) > get<0>(y) ;} ) ;

	//for(auto e : edge ) cout << e.u << " " << e.v << " " << e.weight << " " << e.tin << " " << e.tout << endl ;
	//	cout << endl ;

	for(int i = 1 ; i <= Q ; i++ ) ansQuery[i] = -1 ;

	for(int l = 1 , r = perfectQ ; l <= Q ; l += perfectQ, r += perfectQ )
	{
		if( r > Q ) r = Q ;

		for(int i =1  ; i <= N ; i++ )
		{
			pai[i] = i ;
			componentSize[i] = 1 ;
		}

		vector<Edge> edgeToCheck , edgeForSure ;
		vector<tuple<int,int,int> > queryNow ;

		for(auto e : edge )
		{
			if( e.tin > r || e.tout < l ) continue ;
			if(e.tin <= l && e.tout >= r) edgeForSure.push_back(e) ;
			else edgeToCheck.push_back(e) ;
		}

		for(auto e : queries )
			if(get<2>(e) >= l && get<2>(e) <= r) queryNow.push_back(e) ;

		int ptrForSure = 0 ;
		int tamForSure = sz(edgeForSure) ;
		int tamToCheck = sz(edgeToCheck ) ;

		for(auto e : queryNow )
		{

			int t = get<2>(e) ;
			int startNode = get<1>(e ) ;
			int weight = get<0>(e) ;

			while( ptrForSure < tamForSure && edgeForSure[ptrForSure].weight >= weight )
			{
				join( edgeForSure[ptrForSure].u , edgeForSure[ptrForSure].v ) ;
				ptrForSure++ ;
			}

			for(int i = 0 ; i < tamToCheck ; i++ )
			{
				if( edgeToCheck[i].weight < weight ) break ;
				if( edgeToCheck[i].tin <= t && edgeToCheck[i].tout >= t )
				{

					int x = find( edgeToCheck[i].u ) ;
					int y = find(edgeToCheck[i].v ) ;
					
					adj[x].push_back(y) ;
					adj[y].push_back(x) ;

				}
			}

			startNode = find(startNode) ;
			cnt = 0 ;

			dfs(startNode) ;

			vis[startNode] = false ;
			ansQuery[ t ] = cnt ;

			for(int i = 0 ; i < tamToCheck ; i++ )
			{
				if( edgeToCheck[i].weight < weight ) break ;
				if( edgeToCheck[i].tin <= t && edgeToCheck[i].tout >= t )
				{
					int x = find( edgeToCheck[i].u ) ;
					int y = find(edgeToCheck[i].v ) ;
					
					adj[x].clear() ;
					adj[y].clear() ;

					vis[x] = vis[y] = false ;
				}
			}

		}

	}

	for(int i = 1 ; i <= Q ; i++ )
		if(ansQuery[i] > -1 ) printf("%d\n" , ansQuery[i] ) ;

}

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1536 KB Output is correct
2 Correct 1 ms 1536 KB Output is correct
3 Correct 57 ms 2172 KB Output is correct
4 Correct 6 ms 1984 KB Output is correct
5 Correct 28 ms 2088 KB Output is correct
6 Correct 23 ms 2044 KB Output is correct
7 Correct 27 ms 1920 KB Output is correct
8 Correct 25 ms 2024 KB Output is correct
9 Correct 37 ms 1920 KB Output is correct
10 Correct 27 ms 2024 KB Output is correct
11 Correct 25 ms 2024 KB Output is correct
12 Correct 31 ms 2048 KB Output is correct
13 Correct 35 ms 2048 KB Output is correct
14 Correct 31 ms 2048 KB Output is correct
15 Correct 31 ms 2048 KB Output is correct
16 Correct 28 ms 2024 KB Output is correct
17 Correct 27 ms 2048 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1341 ms 12292 KB Output is correct
2 Correct 1366 ms 12112 KB Output is correct
3 Correct 1369 ms 12184 KB Output is correct
4 Correct 1395 ms 12588 KB Output is correct
5 Correct 1413 ms 12420 KB Output is correct
6 Correct 2625 ms 11200 KB Output is correct
7 Correct 2461 ms 10920 KB Output is correct
8 Correct 2401 ms 11244 KB Output is correct
9 Correct 99 ms 4848 KB Output is correct
10 Correct 1766 ms 10988 KB Output is correct
11 Correct 1575 ms 11168 KB Output is correct
12 Correct 1049 ms 10620 KB Output is correct
13 Correct 1158 ms 12008 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1180 ms 9812 KB Output is correct
2 Correct 1300 ms 6540 KB Output is correct
3 Correct 1555 ms 9552 KB Output is correct
4 Correct 1189 ms 9708 KB Output is correct
5 Correct 100 ms 4716 KB Output is correct
6 Correct 1414 ms 9796 KB Output is correct
7 Correct 1042 ms 9796 KB Output is correct
8 Correct 845 ms 9788 KB Output is correct
9 Correct 629 ms 8848 KB Output is correct
10 Correct 494 ms 8848 KB Output is correct
11 Correct 750 ms 10012 KB Output is correct
12 Correct 617 ms 9968 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 833 ms 14732 KB Output is correct
2 Correct 99 ms 4712 KB Output is correct
3 Correct 90 ms 11276 KB Output is correct
4 Correct 87 ms 11400 KB Output is correct
5 Correct 758 ms 13560 KB Output is correct
6 Correct 812 ms 14852 KB Output is correct
7 Correct 763 ms 13536 KB Output is correct
8 Correct 483 ms 10288 KB Output is correct
9 Correct 495 ms 10264 KB Output is correct
10 Correct 498 ms 9964 KB Output is correct
11 Correct 789 ms 13192 KB Output is correct
12 Correct 770 ms 13376 KB Output is correct
13 Correct 786 ms 13228 KB Output is correct
14 Correct 761 ms 13680 KB Output is correct
15 Correct 769 ms 13652 KB Output is correct
16 Correct 883 ms 15096 KB Output is correct
17 Correct 889 ms 14920 KB Output is correct
18 Correct 881 ms 15140 KB Output is correct
19 Correct 897 ms 14916 KB Output is correct
20 Correct 851 ms 13704 KB Output is correct
21 Correct 829 ms 13736 KB Output is correct
22 Correct 854 ms 14800 KB Output is correct
23 Correct 743 ms 12436 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1341 ms 12292 KB Output is correct
2 Correct 1366 ms 12112 KB Output is correct
3 Correct 1369 ms 12184 KB Output is correct
4 Correct 1395 ms 12588 KB Output is correct
5 Correct 1413 ms 12420 KB Output is correct
6 Correct 2625 ms 11200 KB Output is correct
7 Correct 2461 ms 10920 KB Output is correct
8 Correct 2401 ms 11244 KB Output is correct
9 Correct 99 ms 4848 KB Output is correct
10 Correct 1766 ms 10988 KB Output is correct
11 Correct 1575 ms 11168 KB Output is correct
12 Correct 1049 ms 10620 KB Output is correct
13 Correct 1158 ms 12008 KB Output is correct
14 Correct 1180 ms 9812 KB Output is correct
15 Correct 1300 ms 6540 KB Output is correct
16 Correct 1555 ms 9552 KB Output is correct
17 Correct 1189 ms 9708 KB Output is correct
18 Correct 100 ms 4716 KB Output is correct
19 Correct 1414 ms 9796 KB Output is correct
20 Correct 1042 ms 9796 KB Output is correct
21 Correct 845 ms 9788 KB Output is correct
22 Correct 629 ms 8848 KB Output is correct
23 Correct 494 ms 8848 KB Output is correct
24 Correct 750 ms 10012 KB Output is correct
25 Correct 617 ms 9968 KB Output is correct
26 Correct 1478 ms 12356 KB Output is correct
27 Correct 1855 ms 12164 KB Output is correct
28 Correct 1456 ms 12316 KB Output is correct
29 Correct 878 ms 12132 KB Output is correct
30 Correct 1877 ms 12664 KB Output is correct
31 Correct 1932 ms 12008 KB Output is correct
32 Correct 1908 ms 12184 KB Output is correct
33 Correct 1473 ms 12332 KB Output is correct
34 Correct 1475 ms 12448 KB Output is correct
35 Correct 1486 ms 12264 KB Output is correct
36 Correct 958 ms 12336 KB Output is correct
37 Correct 945 ms 12260 KB Output is correct
38 Correct 937 ms 12220 KB Output is correct
39 Correct 650 ms 11336 KB Output is correct
40 Correct 617 ms 11044 KB Output is correct
41 Correct 625 ms 10980 KB Output is correct
42 Correct 633 ms 12776 KB Output is correct
43 Correct 616 ms 12776 KB Output is correct
44 Correct 600 ms 12648 KB Output is correct

Subtask #6
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1536 KB Output is correct
2 Correct 1 ms 1536 KB Output is correct
3 Correct 57 ms 2172 KB Output is correct
4 Correct 6 ms 1984 KB Output is correct
5 Correct 28 ms 2088 KB Output is correct
6 Correct 23 ms 2044 KB Output is correct
7 Correct 27 ms 1920 KB Output is correct
8 Correct 25 ms 2024 KB Output is correct
9 Correct 37 ms 1920 KB Output is correct
10 Correct 27 ms 2024 KB Output is correct
11 Correct 25 ms 2024 KB Output is correct
12 Correct 31 ms 2048 KB Output is correct
13 Correct 35 ms 2048 KB Output is correct
14 Correct 31 ms 2048 KB Output is correct
15 Correct 31 ms 2048 KB Output is correct
16 Correct 28 ms 2024 KB Output is correct
17 Correct 27 ms 2048 KB Output is correct
18 Correct 1341 ms 12292 KB Output is correct
19 Correct 1366 ms 12112 KB Output is correct
20 Correct 1369 ms 12184 KB Output is correct
21 Correct 1395 ms 12588 KB Output is correct
22 Correct 1413 ms 12420 KB Output is correct
23 Correct 2625 ms 11200 KB Output is correct
24 Correct 2461 ms 10920 KB Output is correct
25 Correct 2401 ms 11244 KB Output is correct
26 Correct 99 ms 4848 KB Output is correct
27 Correct 1766 ms 10988 KB Output is correct
28 Correct 1575 ms 11168 KB Output is correct
29 Correct 1049 ms 10620 KB Output is correct
30 Correct 1158 ms 12008 KB Output is correct
31 Correct 1180 ms 9812 KB Output is correct
32 Correct 1300 ms 6540 KB Output is correct
33 Correct 1555 ms 9552 KB Output is correct
34 Correct 1189 ms 9708 KB Output is correct
35 Correct 100 ms 4716 KB Output is correct
36 Correct 1414 ms 9796 KB Output is correct
37 Correct 1042 ms 9796 KB Output is correct
38 Correct 845 ms 9788 KB Output is correct
39 Correct 629 ms 8848 KB Output is correct
40 Correct 494 ms 8848 KB Output is correct
41 Correct 750 ms 10012 KB Output is correct
42 Correct 617 ms 9968 KB Output is correct
43 Correct 833 ms 14732 KB Output is correct
44 Correct 99 ms 4712 KB Output is correct
45 Correct 90 ms 11276 KB Output is correct
46 Correct 87 ms 11400 KB Output is correct
47 Correct 758 ms 13560 KB Output is correct
48 Correct 812 ms 14852 KB Output is correct
49 Correct 763 ms 13536 KB Output is correct
50 Correct 483 ms 10288 KB Output is correct
51 Correct 495 ms 10264 KB Output is correct
52 Correct 498 ms 9964 KB Output is correct
53 Correct 789 ms 13192 KB Output is correct
54 Correct 770 ms 13376 KB Output is correct
55 Correct 786 ms 13228 KB Output is correct
56 Correct 761 ms 13680 KB Output is correct
57 Correct 769 ms 13652 KB Output is correct
58 Correct 883 ms 15096 KB Output is correct
59 Correct 889 ms 14920 KB Output is correct
60 Correct 881 ms 15140 KB Output is correct
61 Correct 897 ms 14916 KB Output is correct
62 Correct 851 ms 13704 KB Output is correct
63 Correct 829 ms 13736 KB Output is correct
64 Correct 854 ms 14800 KB Output is correct
65 Correct 743 ms 12436 KB Output is correct
66 Correct 1478 ms 12356 KB Output is correct
67 Correct 1855 ms 12164 KB Output is correct
68 Correct 1456 ms 12316 KB Output is correct
69 Correct 878 ms 12132 KB Output is correct
70 Correct 1877 ms 12664 KB Output is correct
71 Correct 1932 ms 12008 KB Output is correct
72 Correct 1908 ms 12184 KB Output is correct
73 Correct 1473 ms 12332 KB Output is correct
74 Correct 1475 ms 12448 KB Output is correct
75 Correct 1486 ms 12264 KB Output is correct
76 Correct 958 ms 12336 KB Output is correct
77 Correct 945 ms 12260 KB Output is correct
78 Correct 937 ms 12220 KB Output is correct
79 Correct 650 ms 11336 KB Output is correct
80 Correct 617 ms 11044 KB Output is correct
81 Correct 625 ms 10980 KB Output is correct
82 Correct 633 ms 12776 KB Output is correct
83 Correct 616 ms 12776 KB Output is correct
84 Correct 600 ms 12648 KB Output is correct
85 Correct 1649 ms 16912 KB Output is correct
86 Correct 150 ms 11748 KB Output is correct
87 Correct 173 ms 11832 KB Output is correct
88 Correct 1617 ms 15576 KB Output is correct
89 Correct 1634 ms 17276 KB Output is correct
90 Correct 1623 ms 14744 KB Output is correct
91 Correct 1538 ms 12364 KB Output is correct
92 Correct 1533 ms 12520 KB Output is correct
93 Correct 2447 ms 11568 KB Output is correct
94 Correct 1731 ms 15816 KB Output is correct
95 Correct 1687 ms 15596 KB Output is correct
96 Correct 2192 ms 14192 KB Output is correct
97 Correct 1012 ms 14012 KB Output is correct
98 Correct 1127 ms 15448 KB Output is correct
99 Correct 1705 ms 16820 KB Output is correct
100 Correct 1669 ms 16824 KB Output is correct
101 Correct 1732 ms 17016 KB Output is correct
102 Correct 1722 ms 16992 KB Output is correct
103 Correct 2213 ms 14576 KB Output is correct
104 Correct 2210 ms 14888 KB Output is correct
105 Correct 1387 ms 15624 KB Output is correct
106 Correct 1141 ms 15484 KB Output is correct
107 Correct 1255 ms 14292 KB Output is correct
108 Correct 2059 ms 15760 KB Output is correct
109 Correct 2013 ms 13132 KB Output is correct