Submission #374825

# Submission time Handle Problem Language Result Execution time Memory
374825 2021-03-08T09:20:49 Z AriaH Bridges (APIO19_bridges) C++11
59 / 100
3000 ms 4652 KB
/** I can do this all day **/

#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx")
#include <bits/stdc++.h>
using namespace std;

typedef long long                   ll;
typedef long double                 ld;
typedef pair<int,int>               pii;
typedef pair<ll,ll>                 pll;
#define all(x)                      (x).begin(),(x).end()
#define F                           first
#define S                           second
#define Mp                          make_pair
#define SZ(x)			    		(int)x.size()
#define fast_io                     ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define file_io                     freopen("in.txt" , "r+" , stdin) ; freopen("out.txt" , "w+" , stdout);

const int N = 1e5 + 2;
const int N2 = 5e4 + 2;
const int B = 650;

int U[N], V[N], W[N], E[N];

bool cmp(int a, int b)
{
	return W[a] > W[b];
}

pii hist[N];

int n, m, q, ptr, tp[N], fir[N], sec[N], change[N], par[N2], sz[N2], Ans[N], mark[N];

bool cmp2(int i, int j)
{
	return sec[i] > sec[j];
}

int Get(int x)
{
    return (x == par[x]? x : par[x] = Get(par[x]));
}

inline void Unify(int v, int u)
{
    v = Get(v), u = Get(u);
    if(v == u) return;
    if(sz[u] > sz[v]) swap(u, v);
    par[u] = v;
    sz[v] += sz[u];
}

int get(int x) { return (x == par[x]? x : get(par[x])); }

inline void unify(int v, int u)
{
	v = get(v), u = get(u);
	if(v == u)
	{
		hist[ptr ++] = Mp(0, 0);
		return;
	}
	if(sz[u] > sz[v]) swap(u, v);
	par[u] = v;
	sz[v] += sz[u];
	hist[ptr ++] = Mp(u, v);
}

inline void undo()
{
	if(ptr == 0) return;
	pii cu = hist[ptr - 1];
	ptr --;
	par[cu.F] = cu.F;
	sz[cu.S] -= sz[cu.F];
}

void solve(int l, int r)
{
	if(l > r) return;
	for(int i = 1; i <= n; i ++) par[i] = i, sz[i] = 1;
	memset(change, 0, sizeof change);
	memset(mark, 0, sizeof mark);
	vector < int > WTF;
	for(int i = l; i <= r; i ++)
	{
		if(tp[i] == 1)
		{
			if(change[fir[i]]) continue;
			change[fir[i]] = 1;
			WTF.push_back(i);
		}
	}
	for(int i = 1; i <= m; i ++) E[i] = i;
	sort(E + 1, E + m + 1, cmp);
	vector < int > Q;
	for(int i = l; i <= r; i ++)
	{
		if(tp[i] == 1) continue;
		Q.push_back(i);
	}
	sort(all(Q), cmp2);
	int last = 1;
	for(auto i : Q)
	{
		ptr = 0;
		while(last <= m && sec[i] <= W[E[last]])
		{
			if(change[E[last]] == 0)
			{
				Unify(V[E[last]], U[E[last]]);
			}
			last ++;
		}
		for(int j = i; j >= l; j --)
		{
			if(tp[j] == 1)
			{
				if(mark[fir[j]]) continue;
				mark[fir[j]] = 1;
				if(sec[j] < sec[i]) continue;
				unify(V[fir[j]], U[fir[j]]);
			}
		}
		for(int j = i; j >= l; j --) mark[fir[j]] = 0;
		for(auto cu : WTF)
		{
			if(cu <= i) continue;
			if(W[fir[cu]] < sec[i]) continue;
			unify(V[fir[cu]], U[fir[cu]]);

		}
		Ans[i] = sz[get(fir[i])];
		while(ptr)
		{
		    undo();
		}		    
	}
	for(int i = l; i <= r; i ++)
	{
		if(tp[i] == 1)
		{
			W[fir[i]] = sec[i];
		}
	}

}

int main()
{
	scanf("%d%d", &n, &m);
	for(int i = 1; i <= m; i ++)
	{
		scanf("%d%d%d", &V[i], &U[i], &W[i]);
	}
	scanf("%d", &q);
	for(int i = 1; i <= q; i ++)
	{
		scanf("%d%d%d", &tp[i], &fir[i], &sec[i]);
		if(i % B == 0)
		{
			solve(i - B + 1, i);
		}
	}
	solve(q / B * B + 1, q);
	for(int i = 1; i <= q; i ++)
	{
		if(tp[i] == 2) printf("%d\n", Ans[i]);
	}
    return 0;
}

/** test corner cases(n = 1?) watch for overflow or minus indices **/

Compilation message

bridges.cpp: In function 'int main()':
bridges.cpp:152:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  152 |  scanf("%d%d", &n, &m);
      |  ~~~~~^~~~~~~~~~~~~~~~
bridges.cpp:155:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  155 |   scanf("%d%d%d", &V[i], &U[i], &W[i]);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
bridges.cpp:157:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  157 |  scanf("%d", &q);
      |  ~~~~~^~~~~~~~~~
bridges.cpp:160:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  160 |   scanf("%d%d%d", &tp[i], &fir[i], &sec[i]);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
# Verdict Execution time Memory Grader output
1 Correct 1 ms 1132 KB Output is correct
2 Correct 1 ms 1132 KB Output is correct
3 Correct 30 ms 1368 KB Output is correct
4 Correct 18 ms 1260 KB Output is correct
5 Correct 26 ms 1260 KB Output is correct
6 Correct 24 ms 1260 KB Output is correct
7 Correct 25 ms 1260 KB Output is correct
8 Correct 25 ms 1260 KB Output is correct
9 Correct 27 ms 1388 KB Output is correct
10 Correct 26 ms 1260 KB Output is correct
11 Correct 25 ms 1260 KB Output is correct
12 Correct 27 ms 1260 KB Output is correct
13 Correct 33 ms 1260 KB Output is correct
14 Correct 29 ms 1260 KB Output is correct
15 Correct 31 ms 1388 KB Output is correct
16 Correct 27 ms 1260 KB Output is correct
17 Correct 27 ms 1260 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 2092 ms 3988 KB Output is correct
2 Correct 2137 ms 4116 KB Output is correct
3 Correct 2195 ms 3972 KB Output is correct
4 Correct 2083 ms 4284 KB Output is correct
5 Correct 2084 ms 4004 KB Output is correct
6 Correct 2598 ms 4460 KB Output is correct
7 Correct 2585 ms 4252 KB Output is correct
8 Correct 2589 ms 4304 KB Output is correct
9 Correct 167 ms 2924 KB Output is correct
10 Correct 1547 ms 4252 KB Output is correct
11 Correct 1506 ms 4076 KB Output is correct
12 Correct 2024 ms 4456 KB Output is correct
13 Correct 1916 ms 4204 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 1390 ms 3820 KB Output is correct
2 Correct 695 ms 3180 KB Output is correct
3 Correct 1455 ms 3920 KB Output is correct
4 Correct 1369 ms 3948 KB Output is correct
5 Correct 166 ms 2924 KB Output is correct
6 Correct 1424 ms 3692 KB Output is correct
7 Correct 1317 ms 3692 KB Output is correct
8 Correct 1242 ms 3564 KB Output is correct
9 Correct 1202 ms 3900 KB Output is correct
10 Correct 1157 ms 3748 KB Output is correct
11 Correct 1144 ms 3532 KB Output is correct
12 Correct 1048 ms 3532 KB Output is correct
# Verdict Execution time Memory Grader output
1 Execution timed out 3083 ms 4652 KB Time limit exceeded
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 2092 ms 3988 KB Output is correct
2 Correct 2137 ms 4116 KB Output is correct
3 Correct 2195 ms 3972 KB Output is correct
4 Correct 2083 ms 4284 KB Output is correct
5 Correct 2084 ms 4004 KB Output is correct
6 Correct 2598 ms 4460 KB Output is correct
7 Correct 2585 ms 4252 KB Output is correct
8 Correct 2589 ms 4304 KB Output is correct
9 Correct 167 ms 2924 KB Output is correct
10 Correct 1547 ms 4252 KB Output is correct
11 Correct 1506 ms 4076 KB Output is correct
12 Correct 2024 ms 4456 KB Output is correct
13 Correct 1916 ms 4204 KB Output is correct
14 Correct 1390 ms 3820 KB Output is correct
15 Correct 695 ms 3180 KB Output is correct
16 Correct 1455 ms 3920 KB Output is correct
17 Correct 1369 ms 3948 KB Output is correct
18 Correct 166 ms 2924 KB Output is correct
19 Correct 1424 ms 3692 KB Output is correct
20 Correct 1317 ms 3692 KB Output is correct
21 Correct 1242 ms 3564 KB Output is correct
22 Correct 1202 ms 3900 KB Output is correct
23 Correct 1157 ms 3748 KB Output is correct
24 Correct 1144 ms 3532 KB Output is correct
25 Correct 1048 ms 3532 KB Output is correct
26 Correct 2005 ms 4212 KB Output is correct
27 Correct 2268 ms 4076 KB Output is correct
28 Correct 2133 ms 4300 KB Output is correct
29 Correct 1878 ms 4148 KB Output is correct
30 Correct 2318 ms 4140 KB Output is correct
31 Correct 2346 ms 4188 KB Output is correct
32 Correct 2352 ms 4204 KB Output is correct
33 Correct 2156 ms 3996 KB Output is correct
34 Correct 2145 ms 4036 KB Output is correct
35 Correct 2143 ms 4076 KB Output is correct
36 Correct 1919 ms 4068 KB Output is correct
37 Correct 1916 ms 4072 KB Output is correct
38 Correct 1892 ms 3988 KB Output is correct
39 Correct 1846 ms 4076 KB Output is correct
40 Correct 1808 ms 4356 KB Output is correct
41 Correct 1824 ms 4468 KB Output is correct
42 Correct 1661 ms 4092 KB Output is correct
43 Correct 1683 ms 3852 KB Output is correct
44 Correct 1677 ms 3992 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 1 ms 1132 KB Output is correct
2 Correct 1 ms 1132 KB Output is correct
3 Correct 30 ms 1368 KB Output is correct
4 Correct 18 ms 1260 KB Output is correct
5 Correct 26 ms 1260 KB Output is correct
6 Correct 24 ms 1260 KB Output is correct
7 Correct 25 ms 1260 KB Output is correct
8 Correct 25 ms 1260 KB Output is correct
9 Correct 27 ms 1388 KB Output is correct
10 Correct 26 ms 1260 KB Output is correct
11 Correct 25 ms 1260 KB Output is correct
12 Correct 27 ms 1260 KB Output is correct
13 Correct 33 ms 1260 KB Output is correct
14 Correct 29 ms 1260 KB Output is correct
15 Correct 31 ms 1388 KB Output is correct
16 Correct 27 ms 1260 KB Output is correct
17 Correct 27 ms 1260 KB Output is correct
18 Correct 2092 ms 3988 KB Output is correct
19 Correct 2137 ms 4116 KB Output is correct
20 Correct 2195 ms 3972 KB Output is correct
21 Correct 2083 ms 4284 KB Output is correct
22 Correct 2084 ms 4004 KB Output is correct
23 Correct 2598 ms 4460 KB Output is correct
24 Correct 2585 ms 4252 KB Output is correct
25 Correct 2589 ms 4304 KB Output is correct
26 Correct 167 ms 2924 KB Output is correct
27 Correct 1547 ms 4252 KB Output is correct
28 Correct 1506 ms 4076 KB Output is correct
29 Correct 2024 ms 4456 KB Output is correct
30 Correct 1916 ms 4204 KB Output is correct
31 Correct 1390 ms 3820 KB Output is correct
32 Correct 695 ms 3180 KB Output is correct
33 Correct 1455 ms 3920 KB Output is correct
34 Correct 1369 ms 3948 KB Output is correct
35 Correct 166 ms 2924 KB Output is correct
36 Correct 1424 ms 3692 KB Output is correct
37 Correct 1317 ms 3692 KB Output is correct
38 Correct 1242 ms 3564 KB Output is correct
39 Correct 1202 ms 3900 KB Output is correct
40 Correct 1157 ms 3748 KB Output is correct
41 Correct 1144 ms 3532 KB Output is correct
42 Correct 1048 ms 3532 KB Output is correct
43 Execution timed out 3083 ms 4652 KB Time limit exceeded
44 Halted 0 ms 0 KB -