oj.uz

Submission #251238

# Submission time Handle Problem Language Result Execution time Memory
251238 2020-07-20T15:58:43 Z _7_7_ Bridges (APIO19_bridges) C++14
14 / 100
 1532 ms 5564 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();
		int v = p[u];
		st.pop();
		cnt[v] -= 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:93:7: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main () {
       ^
bridges.cpp: In function 'int main()':
bridges.cpp:95: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:97: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:99:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &q);
  ~~~~~^~~~~~~~~~
bridges.cpp:101: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 29 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 1527 ms 4124 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 1201 ms 3604 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 1432 ms 5352 KB Output is correct
2 Correct 49 ms 2044 KB Output is correct
3 Correct 172 ms 4208 KB Output is correct
4 Correct 119 ms 4208 KB Output is correct
5 Correct 1320 ms 5352 KB Output is correct
6 Correct 1437 ms 5356 KB Output is correct
7 Correct 1329 ms 5356 KB Output is correct
8 Correct 782 ms 4080 KB Output is correct
9 Correct 777 ms 4080 KB Output is correct
10 Correct 781 ms 4208 KB Output is correct
11 Correct 1180 ms 4712 KB Output is correct
12 Correct 1165 ms 4716 KB Output is correct
13 Correct 1189 ms 4840 KB Output is correct
14 Correct 1155 ms 5480 KB Output is correct
15 Correct 1262 ms 5476 KB Output is correct
16 Correct 1459 ms 5356 KB Output is correct
17 Correct 1516 ms 5376 KB Output is correct
18 Correct 1532 ms 5280 KB Output is correct
19 Correct 1465 ms 5300 KB Output is correct
20 Correct 1283 ms 5272 KB Output is correct
21 Correct 1268 ms 5424 KB Output is correct
22 Correct 1414 ms 5564 KB Output is correct
23 Correct 1296 ms 4992 KB Output is correct

Subtask #5
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 1527 ms 4124 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 29 ms 640 KB Output isn't correct
4 Halted 0 ms 0 KB -