oj.uz

Submission #319788

# Submission time Handle Problem Language Result Execution time Memory
319788 2020-11-06T12:41:03 Z TeaTime Bridges (APIO19_bridges) C++17
13 / 100
 326 ms 56528 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 long long ll;
typedef long double ld;
#define fastInp cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0);

const ll SZ = 30002, INF = 1e9 + 100, SQ = 3;

ll n, m;
unordered_map<int, unordered_map<int, int>> cur;
vector<pair<int, int>> edges, e;
vector<tuple<int, int, int>> edges2;
vector<tuple<int, int, int>> qs;
map<pair<int, int>, int> ind;

bool u[SZ];

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

vector<int> upd;

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

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);
		ind[{u, v}] = i;
		ind[{v, u}] = i;
		
		e.push_back({ u, v });
		edges.push_back({ u, v });
		if (u > v) swap(u, v);
		cur[u][v] = c;
	}

	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);
			cur[u][v] = c;
			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);
					used[u] = 0;
					used[v] = 0;
				}
			}

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

			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:72:28: warning: unused variable 'v' [-Wunused-variable]
   72 |    int u2 = get<1>(qs[j]), v = get<2>(qs[j]);
      |                            ^
bridges.cpp:89:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   89 |   for (int j = 0; j < wts.size(); j++) {
      |                   ~~^~~~~~~~~~~~
bridges.cpp:99:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   99 |  for (int i = 0; i < wts.size(); i++) {
      |                  ~~^~~~~~~~~~~~
bridges.cpp:100:13: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::tuple<int, int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  100 |   while (j2 < edges2.size() && get<0>(edges2[j2]) >= wts[i]) {
      |          ~~~^~~~~~~~~~~~~~~
bridges.cpp: In function 'int main()':
bridges.cpp:177:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  177 |    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 364 KB Output is correct
3 Correct 228 ms 1164 KB Output is correct
4 Correct 5 ms 812 KB Output is correct
5 Correct 20 ms 816 KB Output is correct
6 Correct 22 ms 876 KB Output is correct
7 Correct 31 ms 804 KB Output is correct
8 Correct 27 ms 876 KB Output is correct
9 Correct 31 ms 748 KB Output is correct
10 Correct 24 ms 876 KB Output is correct
11 Correct 23 ms 908 KB Output is correct
12 Correct 24 ms 876 KB Output is correct
13 Correct 36 ms 876 KB Output is correct
14 Correct 35 ms 876 KB Output is correct
15 Correct 35 ms 876 KB Output is correct
16 Correct 36 ms 808 KB Output is correct
17 Correct 29 ms 804 KB Output is correct

Subtask #2
0 / 16.0

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

Subtask #3
0 / 17.0

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

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Runtime error 326 ms 56528 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 Runtime error 121 ms 38872 KB Execution killed with signal 11 (could be triggered by violating memory limits)
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 364 KB Output is correct
3 Correct 228 ms 1164 KB Output is correct
4 Correct 5 ms 812 KB Output is correct
5 Correct 20 ms 816 KB Output is correct
6 Correct 22 ms 876 KB Output is correct
7 Correct 31 ms 804 KB Output is correct
8 Correct 27 ms 876 KB Output is correct
9 Correct 31 ms 748 KB Output is correct
10 Correct 24 ms 876 KB Output is correct
11 Correct 23 ms 908 KB Output is correct
12 Correct 24 ms 876 KB Output is correct
13 Correct 36 ms 876 KB Output is correct
14 Correct 35 ms 876 KB Output is correct
15 Correct 35 ms 876 KB Output is correct
16 Correct 36 ms 808 KB Output is correct
17 Correct 29 ms 804 KB Output is correct
18 Runtime error 121 ms 38872 KB Execution killed with signal 11 (could be triggered by violating memory limits)
19 Halted 0 ms 0 KB -