oj.uz

Submission #251222

# Submission time Handle Problem Language Result Execution time Memory
251222 2020-07-20T15:46:42 Z _7_7_ Bridges (APIO19_bridges) C++14
14 / 100
 1530 ms 5204 KB 
#include <bits/stdc++.h>                                           
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
 

using namespace std;
using namespace __gnu_pbds;

//#define int long long
//#pragma GCC optimize("Ofast")
//#pragma comment(linker, "/stack:200000000")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4")
 
 
#define file(s) freopen(s".in","r",stdin); freopen(s".out","w",stdout);
#define fastio ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define all(x) x.begin(), x.end()
#define sz(s) (int)s.size()
#define pb push_back
#define ppb pop_back
#define mp make_pair
#define s second
#define f first
 
 

 
 
typedef pair < int, int > pii;
typedef unsigned long long ull;         
typedef vector < pii > vpii;
typedef vector < int > vi;
typedef long double ldb;  
typedef long long ll;  
typedef double db;                             
 
typedef tree<pii, null_type, less<pii>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
 
const int dx[] = {1, -1, 0, 0}, dy[] = {0, 0, 1, -1}, block = 1055;
const int inf = 1e9, maxn = 4e5 + 148, mod = 1e9 + 7, N = 1e5 + 11;
const pii base = mp(1171, 3307), Mod = mp(1e9 + 7, 1e9 + 9);
const db eps = 1e-12, pi = 3.14159265359;
const ll INF = 1e18;

int timer;

struct DSU {
	int p[N], cnt[N];
	stack < int > st;

	void init (int n) {
		while (sz(st))
			st.pop();
		for (int i = 1; i <= n; ++i) {
			p[i] = i;
			cnt[i] = 1;
		}
	}
	
	int get (int v) { 
		return p[v] == v ? v : p[v] = get(p[v]);
	}

	void merge (int v, int u) {
		v = get(v), u = get(u);
		if (v == u)
			return;

		if (cnt[v] < cnt[u])
			swap(v, u);
		p[u] = v;
		cnt[v] += cnt[u];
		st.push(u);
		++timer;
	}

	void undo () {
		int u = st.top();
		st.pop();
		cnt[p[u]] -= cnt[u];
		p[u] = u;
	}
} T;


vi nw;
vpii prv;
bool was[N];
vector < pair < pii, int > > a, b;
int n, m, q, v[N], u[N], w[N], ww[N], x, y, res[N], tp;

main () {
	fastio
	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, &x, &y);	
		if (tp == 1) 
			a.pb({{x, y}, i});
		else
			b.pb({{y, x}, i});

		if (i % block == 0 || i == q) {
			T.init(n);
			for (int i = 1; i <= m; ++i)
				was[i] = 0;

			for (auto x : a)
				was[x.f.f] = 1;

			for (int i = 1; i <= m; ++i)
				if (!was[i])
					prv.pb({w[i], i});
				else
					nw.pb(i);	

			sort(all(b));
			reverse(all(b));
			sort(all(prv));
			reverse(all(prv));
			int j = 0;

			for (auto x : b) {
				while (j < sz(prv) && prv[j].f >= x.f.f) {
					T.merge(v[prv[j].s], u[prv[j].s]);
					++j;
				}

				for (auto y : nw)
					ww[y] = w[y];

				for (auto y : a)
					if (y.s <= x.s)
						ww[y.f.f] = y.f.s;

				timer = 0;
				for (auto y : nw)
					if (ww[y] >= x.f.f)
						T.merge(v[y], u[y]);

				res[x.s] = T.cnt[T.get(x.f.s)];
				while (timer--)
					T.undo();
			}
			
			for (auto y : a)
				w[y.f.f] = y.f.s;
			
			a.clear();
			b.clear();
			nw.clear();
			prv.clear();	
		}
	}
	
	for (int i = 1; i <= q; ++i)
		if (res[i])
			printf("%d\n", res[i]);
}

Compilation message

bridges.cpp:92:7: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main () {
       ^
bridges.cpp: In function 'int main()':
bridges.cpp:94: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:96:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d%d", &v[i], &u[i], &w[i]);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
bridges.cpp:98:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &q);
  ~~~~~^~~~~~~~~~
bridges.cpp:100:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d%d", &tp, &x, &y); 
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 0 ms 512 KB Output is correct
3 Incorrect 28 ms 640 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 16.0

# Verdict Execution time Memory Grader output
1 Incorrect 1530 ms 3756 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 1212 ms 3184 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1419 ms 4844 KB Output is correct
2 Correct 46 ms 1912 KB Output is correct
3 Correct 159 ms 3696 KB Output is correct
4 Correct 118 ms 3696 KB Output is correct
5 Correct 1318 ms 4844 KB Output is correct
6 Correct 1420 ms 5000 KB Output is correct
7 Correct 1347 ms 4868 KB Output is correct
8 Correct 765 ms 3568 KB Output is correct
9 Correct 762 ms 3568 KB Output is correct
10 Correct 776 ms 3812 KB Output is correct
11 Correct 1172 ms 4248 KB Output is correct
12 Correct 1159 ms 4120 KB Output is correct
13 Correct 1199 ms 4396 KB Output is correct
14 Correct 1146 ms 4932 KB Output is correct
15 Correct 1292 ms 5204 KB Output is correct
16 Correct 1512 ms 5092 KB Output is correct
17 Correct 1460 ms 4712 KB Output is correct
18 Correct 1472 ms 4716 KB Output is correct
19 Correct 1510 ms 4868 KB Output is correct
20 Correct 1264 ms 4868 KB Output is correct
21 Correct 1289 ms 4584 KB Output is correct
22 Correct 1445 ms 5008 KB Output is correct
23 Correct 1293 ms 4568 KB Output is correct

Subtask #5
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 1530 ms 3756 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 0 ms 512 KB Output is correct
3 Incorrect 28 ms 640 KB Output isn't correct
4 Halted 0 ms 0 KB -