oj.uz

Submission #319809

# Submission time Handle Problem Language Result Execution time Memory
319809 2020-11-06T13:24:58 Z TeaTime Bridges (APIO19_bridges) C++17
13 / 100
 3000 ms 127488 KB 
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <set>
#include <map>
#include <queue>
#include <random>
#include <chrono>
#include <tuple>
#include <random>
#include <cmath>
#include <unordered_map>
#include <bitset>

using namespace std;

typedef int ll;
typedef long double ld;
#define fastInp cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0);

const ll SZ = 50002, INF = 1e9 + 100, SQ = 300;

ll n, m;
vector<pair<int, int>> edges, e;
vector<tuple<int, int, int>> edges2;
vector<tuple<int, int, int>> qs;

bool u[SZ];

vector<ll> wts;
vector<int> shit;

vector<int> upd;

int dsu[SZ][SQ + 5], s[SZ][SQ + 5];

int find(int v, int i) {
	if (dsu[v][i] == v) return v;
	else return dsu[v][i] = find(dsu[v][i], i);
}

void uni(int v, int u, int i) {
	u = find(u, i);
	v = find(v, i);

	if (u != v) {
		if (s[v] < s[u]) {
			swap(u, v);
		}

		dsu[u][i] = v;
		s[v][i] += s[u][i];
	}
}

void build(int i) {
	bool fl = 0;
	wts.clear();
	edges2.clear();
	upd.clear();
	for (int i = 0; i < m; i++) u[i] = 0;

	for (int j = i; j < min(ll(qs.size()), i + SQ); j++) {
		if (get<0>(qs[j]) == 2) {
			fl = 1;
			wts.push_back(get<2>(qs[j]));
		}
		if (get<0>(qs[j]) == 1) {
			int u2 = get<1>(qs[j]), v = get<2>(qs[j]);
			u[u2] = 1;
			upd.push_back(u2);
		}
	}
	
	if (!fl) return;

	for (int i = 0; i < m; i++) {
		if (u[i]) continue;
		pair<ll, ll> c = edges[i];
		edges2.push_back({ shit[i], c.first, c.second });
	}

	sort(edges2.rbegin(), edges2.rend());

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < wts.size(); j++) {
			dsu[i][j] = i;
			s[i][j] = 1;
		}
	}

	sort(wts.rbegin(), wts.rend());

	ll j2 = 0;

	for (int i = 0; i < wts.size(); i++) {
		while (j2 < edges2.size() && get<0>(edges2[j2]) >= wts[i]) {
			uni(get<1>(edges2[j2]), get<2>(edges2[j2]), i);
			j2++;
		}

		for (int t = 0; t < n; t++) {
			dsu[t][i + 1] = dsu[t][i];
			s[t][i + 1] = s[t][i];
		}
	}
}

vector<vector<ll>> gr;
bool used[SZ];

int dfs(int v, int i) {
	used[v] = 1;

	int ss = 0;
	for (auto to : gr[v]) {
		if (!used[to]) ss += dfs(to, i);
	}

	return ss + s[v][i];
}

int main()
{
	fastInp;

	cin >> n >> m;
	
	for (int i = 0; i < m; i++) {
		int u, v, c;
		cin >> u >> v >> c;
		u--; v--;
		shit.push_back(c);
		e.push_back({ u, v });
		edges.push_back({ u, v });
		if (u > v) swap(u, v);
	}

	ll q;
	cin >> q;

	for (int i = 0; i < q; i++) {
		int a, b, c;
		cin >> a >> b >> c;
		b--;
		qs.push_back({ a, b, c });
	}

	gr.resize(n);
	for (int i = 0; i < q; i++) {
		if (i % SQ == 0) {
			build(i);
		}

		if (get<0>(qs[i]) == 1) {
			int c, j;
			j = get<1>(qs[i]);
			c = get<2>(qs[i]);
			ll u = e[j].first, v = e[j].second;
			if (u > v) swap(u, v);
			shit[j] = c;
		}
		else {
			int v, w;
			v = get<1>(qs[i]);
			w = get<2>(qs[i]);

			int i2 = 0;
			for (i2 = 0; i2 < wts.size(); i2++) {
				if (wts[i2] == w) break;
			}

			for (auto c : upd) {
				int u = e[c].first, v = e[c].second;

				if (u > v) swap(u, v);
				if (shit[c] >= w) {
					u = find(u, i2);
					v = find(v, i2);
					gr[u].push_back(v);
					gr[v].push_back(u);
				}
			}

			cout << dfs(find(v, i2), i2) << "\n";

			used[find(v, i2)] = 0;

			for (auto c : upd) {
				int u = e[c].first, v = e[c].second;

				if (u > v) swap(u, v);
				if (shit[c] >= w) {
					u = find(u, i2);
					v = find(v, i2);
					gr[u].pop_back();
					gr[v].pop_back();
					used[u] = 0;
					used[v] = 0;
				}
			}
		}
	}

	return 0;
}

/*
5
1 4 1 3 5
2 1 4 1 2
5 1 1 4 5
3 5 1 1 2
4 3 5 1 1

3
1 1 1
2 2 2
3 3 3
*/

Compilation message

bridges.cpp: In function 'void build(int)':
bridges.cpp:70:28: warning: unused variable 'v' [-Wunused-variable]
   70 |    int u2 = get<1>(qs[j]), v = get<2>(qs[j]);
      |                            ^
bridges.cpp:87:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   87 |   for (int j = 0; j < wts.size(); j++) {
      |                   ~~^~~~~~~~~~~~
bridges.cpp:97:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   97 |  for (int i = 0; i < wts.size(); i++) {
      |                  ~~^~~~~~~~~~~~
bridges.cpp:98:13: warning: comparison of integer expressions of different signedness: 'll' {aka 'int'} and 'std::vector<std::tuple<int, int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   98 |   while (j2 < edges2.size() && get<0>(edges2[j2]) >= wts[i]) {
      |          ~~~^~~~~~~~~~~~~~~
bridges.cpp: In function 'int main()':
bridges.cpp:170:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  170 |    for (i2 = 0; i2 < wts.size(); i2++) {
      |                 ~~~^~~~~~~~~~~~

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 368 KB Output is correct
3 Correct 42 ms 1072 KB Output is correct
4 Correct 7 ms 836 KB Output is correct
5 Correct 36 ms 864 KB Output is correct
6 Correct 28 ms 816 KB Output is correct
7 Correct 31 ms 944 KB Output is correct
8 Correct 30 ms 1072 KB Output is correct
9 Correct 40 ms 944 KB Output is correct
10 Correct 31 ms 1072 KB Output is correct
11 Correct 32 ms 1072 KB Output is correct
12 Correct 32 ms 1072 KB Output is correct
13 Correct 39 ms 1068 KB Output is correct
14 Correct 34 ms 1068 KB Output is correct
15 Correct 36 ms 1068 KB Output is correct
16 Correct 34 ms 944 KB Output is correct
17 Correct 34 ms 944 KB Output is correct

Subtask #2
0 / 16.0

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

Subtask #3
0 / 17.0

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

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Runtime error 85 ms 14028 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #5
0 / 13.0

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

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 368 KB Output is correct
3 Correct 42 ms 1072 KB Output is correct
4 Correct 7 ms 836 KB Output is correct
5 Correct 36 ms 864 KB Output is correct
6 Correct 28 ms 816 KB Output is correct
7 Correct 31 ms 944 KB Output is correct
8 Correct 30 ms 1072 KB Output is correct
9 Correct 40 ms 944 KB Output is correct
10 Correct 31 ms 1072 KB Output is correct
11 Correct 32 ms 1072 KB Output is correct
12 Correct 32 ms 1072 KB Output is correct
13 Correct 39 ms 1068 KB Output is correct
14 Correct 34 ms 1068 KB Output is correct
15 Correct 36 ms 1068 KB Output is correct
16 Correct 34 ms 944 KB Output is correct
17 Correct 34 ms 944 KB Output is correct
18 Execution timed out 3099 ms 127488 KB Time limit exceeded
19 Halted 0 ms 0 KB -