oj.uz

Submission #251201

# Submission time Handle Problem Language Result Execution time Memory
251201 2020-07-20T15:03:27 Z _7_7_ Bridges (APIO19_bridges) C++14
14 / 100
 1537 ms 7912 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 : 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], tp, x, y, ww[N], res[N];


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 == q || i % block == 0) {
			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();
			}

			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 1 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Incorrect 34 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 1503 ms 5588 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 4616 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 1514 ms 7864 KB Output is correct
2 Correct 50 ms 2424 KB Output is correct
3 Correct 171 ms 4720 KB Output is correct
4 Correct 138 ms 4848 KB Output is correct
5 Correct 1407 ms 6232 KB Output is correct
6 Correct 1490 ms 7784 KB Output is correct
7 Correct 1447 ms 6256 KB Output is correct
8 Correct 772 ms 5488 KB Output is correct
9 Correct 750 ms 5532 KB Output is correct
10 Correct 758 ms 5424 KB Output is correct
11 Correct 1167 ms 6368 KB Output is correct
12 Correct 1115 ms 6488 KB Output is correct
13 Correct 1148 ms 6688 KB Output is correct
14 Correct 1237 ms 6280 KB Output is correct
15 Correct 1366 ms 6368 KB Output is correct
16 Correct 1504 ms 7660 KB Output is correct
17 Correct 1537 ms 7724 KB Output is correct
18 Correct 1511 ms 7912 KB Output is correct
19 Correct 1501 ms 7820 KB Output is correct
20 Correct 1318 ms 6892 KB Output is correct
21 Correct 1311 ms 7016 KB Output is correct
22 Correct 1474 ms 7532 KB Output is correct
23 Correct 1339 ms 5692 KB Output is correct

Subtask #5
0 / 13.0

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