oj.uz

Submission #972562

# Submission time Handle Problem Language Result Execution time Memory
972562 2024-04-30T15:20:20 Z pan Bridges (APIO19_bridges) C++17
59 / 100
 3000 ms 15100 KB 
#include <bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
//#include "bits_stdc++.h"
#define endl '\n'
#define f first
#define s second
#define pb push_back
#define mp make_pair
#define lb lower_bound
#define ub upper_bound
#define input(x) scanf("%lld", &x);
#define input2(x, y) scanf("%lld%lld", &x, &y);
#define input3(x, y, z) scanf("%lld%lld%lld", &x, &y, &z);
#define input4(x, y, z, a) scanf("%lld%lld%lld%lld", &x, &y, &z, &a);
#define print(x, y) printf("%lld%c", x, y);
#define show(x) cerr << #x << " is " << x << endl;
#define show2(x,y) cerr << #x << " is " << x << " " << #y << " is " << y << endl;
#define show3(x,y,z) cerr << #x << " is " << x << " " << #y << " is " << y << " " << #z << " is " << z << endl;
#define all(x) x.begin(), x.end()
#define discretize(x) sort(x.begin(), x.end()); x.erase(unique(x.begin(), x.end()), x.end());
using namespace std;
//using namespace __gnu_pbds;
//#define ordered_set tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>
//#define ordered_multiset tree<int, null_type, less_equal<int>, rb_tree_tag, tree_order_statistics_node_update>
typedef long long ll;
typedef __int128  sll;
typedef long double ld;
typedef pair<ld, ll> pd;
typedef pair<string, ll> psl;
typedef pair<ll, ll> pi;
typedef pair<ll, pi> pii;
typedef pair<pi, pi> piii;
ll const blk = 320;
ll n, m, q, t, l, r, counter;
ll par[100005], siz[100005], ans[100005];
ll weight[100005];
pii queries[100005];
pi co[100005];
bool ban[100005];
ll newweight[100005];
vector<ll> op;

void init()
{
	for (ll i=1; i<=n; ++i) par[i] = i;
	fill(siz+1, siz+n+1, 1);
	op.clear();
}

inline ll find(ll x)
{
	while (par[x]!=x) x= par[x];
	return x;
}

void unite(ll x, ll y)
{
	//show2(x,y);
	x = find(x), y = find(y);
	if (x==y) return;
	if (siz[x] > siz[y]) swap(x,y); // only union by rank work
	//show2(x,y);
	op.pb(x);
	counter++;
	siz[y]+=siz[x];
	par[x] = par[y];
	//show(siz[y]);
}

void rollback(ll x)
{
	//show(x);
	while (op.size() && x--) 
	{
		//show(op.back());
		ll now = op.back();
		op.pop_back();
		siz[par[now]] -= siz[now];
		par[now]= now;
	}
}



int main()
{
	input2(n, m);
	for (ll i=1; i<=m; ++i) input3(co[i].f, co[i].s, weight[i]);
	input(q);
	for (ll i=0; i<q; ++i) {input3(queries[i].f, queries[i].s.f, queries[i].s.s); if (queries[i].f==2) swap(queries[i].s.f, queries[i].s.s); }
	ll ind = -1;
	fill(ban+1, ban+m+1, 0);
	while (ind+1<q)
	{
		init();
		ll start = ind+1, end = min(ind+blk, q-1);
		vector<pi> edges, answer;
		vector<ll> update;
		for (ll i=start; i<=end; ++i)
		{
			if (queries[i].f==1) {ban[queries[i].s.f] = 1; update.pb(i);}
			else {answer.pb(mp(queries[i].s.f, i));}
		}
		for (ll i=1; i<=m; ++i) if (!ban[i]) edges.pb(mp(weight[i], i));
		sort(edges.begin(), edges.end(), greater<pi>());
		sort(answer.begin(), answer.end(), greater<pi>());
		ll slide = -1;
		for (pi u: answer)
		{
			//show2(u.f, u.s);
			ll where = queries[u.s].s.s;
			while (slide+1<edges.size() && edges[slide+1].f>=u.f)
			{
				slide++;
				ll i = edges[slide].s;
				unite(co[i].f, co[i].s);
				//show(i);
			}
			counter = 0;
			unordered_map<ll, ll> mapp;
			for (ll x: update)
			{
				ll which = queries[x].s.f;
				if (x>u.s && mapp.find(which)==mapp.end()) mapp[which] = weight[which];
				else if (x<u.s) mapp[which] = queries[x].s.s;
			}
			for (auto it = mapp.begin(); it!=mapp.end(); ++it) if (it->s>=u.f) {unite(co[it->f].f, co[it->f].s);}
			//show2(where, find(where));
			ans[u.s] = siz[find(where)];
			rollback(counter);
		}
		for (ll x: update) {weight[queries[x].s.f] = queries[x].s.s, ban[queries[x].s.f] = 0;}
		ind+=blk;
	}
	for (ll i=0; i<q; ++i) if (queries[i].f==2) { print(ans[i], '\n');}
	return 0;
}

Compilation message

bridges.cpp: In function 'int main()':
bridges.cpp:113:18: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  113 |    while (slide+1<edges.size() && edges[slide+1].f>=u.f)
      |           ~~~~~~~^~~~~~~~~~~~~
bridges.cpp:13:27: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   13 | #define input2(x, y) scanf("%lld%lld", &x, &y);
      |                      ~~~~~^~~~~~~~~~~~~~~~~~~~
bridges.cpp:88:2: note: in expansion of macro 'input2'
   88 |  input2(n, m);
      |  ^~~~~~
bridges.cpp:14:30: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   14 | #define input3(x, y, z) scanf("%lld%lld%lld", &x, &y, &z);
      |                         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
bridges.cpp:89:26: note: in expansion of macro 'input3'
   89 |  for (ll i=1; i<=m; ++i) input3(co[i].f, co[i].s, weight[i]);
      |                          ^~~~~~
bridges.cpp:12:23: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   12 | #define input(x) scanf("%lld", &x);
      |                  ~~~~~^~~~~~~~~~~~
bridges.cpp:90:2: note: in expansion of macro 'input'
   90 |  input(q);
      |  ^~~~~
bridges.cpp:14:30: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   14 | #define input3(x, y, z) scanf("%lld%lld%lld", &x, &y, &z);
      |                         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
bridges.cpp:91:26: note: in expansion of macro 'input3'
   91 |  for (ll i=0; i<q; ++i) {input3(queries[i].f, queries[i].s.f, queries[i].s.s); if (queries[i].f==2) swap(queries[i].s.f, queries[i].s.s); }
      |                          ^~~~~~

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6488 KB Output is correct
2 Correct 1 ms 6492 KB Output is correct
3 Correct 39 ms 6808 KB Output is correct
4 Correct 4 ms 4696 KB Output is correct
5 Correct 22 ms 6744 KB Output is correct
6 Correct 21 ms 6752 KB Output is correct
7 Correct 23 ms 6492 KB Output is correct
8 Correct 23 ms 6760 KB Output is correct
9 Correct 23 ms 6492 KB Output is correct
10 Correct 23 ms 6748 KB Output is correct
11 Correct 22 ms 6744 KB Output is correct
12 Correct 23 ms 6748 KB Output is correct
13 Correct 27 ms 6748 KB Output is correct
14 Correct 26 ms 6748 KB Output is correct
15 Correct 24 ms 6744 KB Output is correct
16 Correct 22 ms 6492 KB Output is correct
17 Correct 23 ms 6488 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 2004 ms 12616 KB Output is correct
2 Correct 2035 ms 12600 KB Output is correct
3 Correct 2056 ms 12824 KB Output is correct
4 Correct 2090 ms 12648 KB Output is correct
5 Correct 2036 ms 12884 KB Output is correct
6 Correct 2021 ms 12632 KB Output is correct
7 Correct 2089 ms 12640 KB Output is correct
8 Correct 2108 ms 12672 KB Output is correct
9 Correct 30 ms 5968 KB Output is correct
10 Correct 1643 ms 11488 KB Output is correct
11 Correct 1812 ms 11444 KB Output is correct
12 Correct 1741 ms 12816 KB Output is correct
13 Correct 1834 ms 12816 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1514 ms 10940 KB Output is correct
2 Correct 664 ms 8808 KB Output is correct
3 Correct 1435 ms 10628 KB Output is correct
4 Correct 1479 ms 11164 KB Output is correct
5 Correct 33 ms 5972 KB Output is correct
6 Correct 1474 ms 10780 KB Output is correct
7 Correct 1399 ms 10800 KB Output is correct
8 Correct 1381 ms 10820 KB Output is correct
9 Correct 1140 ms 10900 KB Output is correct
10 Correct 1139 ms 11056 KB Output is correct
11 Correct 1201 ms 10788 KB Output is correct
12 Correct 1184 ms 11052 KB Output is correct

Subtask #4
0 / 14.0

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

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 2004 ms 12616 KB Output is correct
2 Correct 2035 ms 12600 KB Output is correct
3 Correct 2056 ms 12824 KB Output is correct
4 Correct 2090 ms 12648 KB Output is correct
5 Correct 2036 ms 12884 KB Output is correct
6 Correct 2021 ms 12632 KB Output is correct
7 Correct 2089 ms 12640 KB Output is correct
8 Correct 2108 ms 12672 KB Output is correct
9 Correct 30 ms 5968 KB Output is correct
10 Correct 1643 ms 11488 KB Output is correct
11 Correct 1812 ms 11444 KB Output is correct
12 Correct 1741 ms 12816 KB Output is correct
13 Correct 1834 ms 12816 KB Output is correct
14 Correct 1514 ms 10940 KB Output is correct
15 Correct 664 ms 8808 KB Output is correct
16 Correct 1435 ms 10628 KB Output is correct
17 Correct 1479 ms 11164 KB Output is correct
18 Correct 33 ms 5972 KB Output is correct
19 Correct 1474 ms 10780 KB Output is correct
20 Correct 1399 ms 10800 KB Output is correct
21 Correct 1381 ms 10820 KB Output is correct
22 Correct 1140 ms 10900 KB Output is correct
23 Correct 1139 ms 11056 KB Output is correct
24 Correct 1201 ms 10788 KB Output is correct
25 Correct 1184 ms 11052 KB Output is correct
26 Correct 2102 ms 12596 KB Output is correct
27 Correct 2092 ms 12412 KB Output is correct
28 Correct 2105 ms 12620 KB Output is correct
29 Correct 2069 ms 12588 KB Output is correct
30 Correct 2113 ms 12692 KB Output is correct
31 Correct 2075 ms 12476 KB Output is correct
32 Correct 2100 ms 12428 KB Output is correct
33 Correct 2041 ms 12620 KB Output is correct
34 Correct 2089 ms 12620 KB Output is correct
35 Correct 2174 ms 12616 KB Output is correct
36 Correct 1986 ms 12568 KB Output is correct
37 Correct 2021 ms 13296 KB Output is correct
38 Correct 2057 ms 12564 KB Output is correct
39 Correct 1753 ms 12836 KB Output is correct
40 Correct 1745 ms 12712 KB Output is correct
41 Correct 1745 ms 12540 KB Output is correct
42 Correct 1742 ms 12556 KB Output is correct
43 Correct 1803 ms 12536 KB Output is correct
44 Correct 1803 ms 12560 KB Output is correct

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6488 KB Output is correct
2 Correct 1 ms 6492 KB Output is correct
3 Correct 39 ms 6808 KB Output is correct
4 Correct 4 ms 4696 KB Output is correct
5 Correct 22 ms 6744 KB Output is correct
6 Correct 21 ms 6752 KB Output is correct
7 Correct 23 ms 6492 KB Output is correct
8 Correct 23 ms 6760 KB Output is correct
9 Correct 23 ms 6492 KB Output is correct
10 Correct 23 ms 6748 KB Output is correct
11 Correct 22 ms 6744 KB Output is correct
12 Correct 23 ms 6748 KB Output is correct
13 Correct 27 ms 6748 KB Output is correct
14 Correct 26 ms 6748 KB Output is correct
15 Correct 24 ms 6744 KB Output is correct
16 Correct 22 ms 6492 KB Output is correct
17 Correct 23 ms 6488 KB Output is correct
18 Correct 2004 ms 12616 KB Output is correct
19 Correct 2035 ms 12600 KB Output is correct
20 Correct 2056 ms 12824 KB Output is correct
21 Correct 2090 ms 12648 KB Output is correct
22 Correct 2036 ms 12884 KB Output is correct
23 Correct 2021 ms 12632 KB Output is correct
24 Correct 2089 ms 12640 KB Output is correct
25 Correct 2108 ms 12672 KB Output is correct
26 Correct 30 ms 5968 KB Output is correct
27 Correct 1643 ms 11488 KB Output is correct
28 Correct 1812 ms 11444 KB Output is correct
29 Correct 1741 ms 12816 KB Output is correct
30 Correct 1834 ms 12816 KB Output is correct
31 Correct 1514 ms 10940 KB Output is correct
32 Correct 664 ms 8808 KB Output is correct
33 Correct 1435 ms 10628 KB Output is correct
34 Correct 1479 ms 11164 KB Output is correct
35 Correct 33 ms 5972 KB Output is correct
36 Correct 1474 ms 10780 KB Output is correct
37 Correct 1399 ms 10800 KB Output is correct
38 Correct 1381 ms 10820 KB Output is correct
39 Correct 1140 ms 10900 KB Output is correct
40 Correct 1139 ms 11056 KB Output is correct
41 Correct 1201 ms 10788 KB Output is correct
42 Correct 1184 ms 11052 KB Output is correct
43 Execution timed out 3040 ms 15100 KB Time limit exceeded
44 Halted 0 ms 0 KB -