oj.uz

Submission #251244

# Submission time Handle Problem Language Result Execution time Memory
251244 2020-07-20T16:04:46 Z _7_7_ Bridges (APIO19_bridges) C++14
14 / 100
 1531 ms 4464 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) {
		for (int i = 1; i <= n; ++i) {
			p[i] = i;
			cnt[i] = 1;
		}

		while (sz(st))
			st.pop();
	}
	
	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);   	
		st.push(u);
		p[u] = v;
		cnt[v] += cnt[u];
		++timer;
	}

	void undo () {
		int u = st.top();
		int v = p[u];
		st.pop();
		p[u] = u;
		cnt[v] -= cnt[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;

			sort(all(b));
			reverse(all(b));

			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(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:94:7: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main () {
       ^
bridges.cpp: In function 'int main()':
bridges.cpp:96: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:98: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:100:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &q);
  ~~~~~^~~~~~~~~~
bridges.cpp:102: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 1 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Incorrect 34 ms 632 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 16.0

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

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 1170 ms 2568 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 1407 ms 4292 KB Output is correct
2 Correct 49 ms 1144 KB Output is correct
3 Correct 171 ms 3108 KB Output is correct
4 Correct 121 ms 3184 KB Output is correct
5 Correct 1287 ms 4464 KB Output is correct
6 Correct 1416 ms 4332 KB Output is correct
7 Correct 1348 ms 4428 KB Output is correct
8 Correct 820 ms 2996 KB Output is correct
9 Correct 793 ms 2948 KB Output is correct
10 Correct 810 ms 3220 KB Output is correct
11 Correct 1162 ms 3592 KB Output is correct
12 Correct 1150 ms 3636 KB Output is correct
13 Correct 1192 ms 3744 KB Output is correct
14 Correct 1164 ms 4400 KB Output is correct
15 Correct 1282 ms 4288 KB Output is correct
16 Correct 1531 ms 4180 KB Output is correct
17 Correct 1515 ms 4272 KB Output is correct
18 Correct 1455 ms 4144 KB Output is correct
19 Correct 1444 ms 4204 KB Output is correct
20 Correct 1361 ms 4044 KB Output is correct
21 Correct 1352 ms 4032 KB Output is correct
22 Correct 1444 ms 4292 KB Output is correct
23 Correct 1311 ms 3984 KB Output is correct

Subtask #5
0 / 13.0

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

Subtask #6
0 / 27.0

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