oj.uz

Submission #156955

# Submission time Handle Problem Language Result Execution time Memory
156955 2019-10-08T12:57:07 Z popovicirobert Bridges (APIO19_bridges) C++14
100 / 100
 2849 ms 21292 KB 
#include <bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define lsb(x) (x & (-x)) 
    
using namespace std;

const int MAXN = 50000;
const int MAXM = (int) 1e5;
const int B = 1500;

struct DSU {
	vector <int> par, sz;
	int n;

	inline void init(int _n) {
		n = _n;
		par.resize(n + 1), sz.resize(n + 1, 1);
	}

	int root(int x) {
		if(par[x] == 0) return x;
		return par[x] = root(par[x]);
	}

	inline void join(int x, int y) {
		x = root(x), y = root(y);
		if(x != y) {
			par[x] = y;
			sz[y] += sz[x];
		}
	}
};

struct Query {
	int a, b, type;
};

struct Data {
	int w, nod, pos;
	bool operator <(const Data &other) const {
		return w < other.w;
	}
};
   
int main() {
#if 0
    ifstream cin("A.in");
    ofstream cout("A.out");
#endif
    int i, j, n, m, q;
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
	
	cin >> n >> m;
	vector < vector < pair <int, int> > > g(n + 1);
	vector <int> weight(m + 1), x(m + 1), y(m + 1);

	for(i = 1; i <= m; i++) {
		cin >> x[i] >> y[i] >> weight[i];
		g[x[i]].push_back({y[i], i});
		g[y[i]].push_back({x[i], i});
	}

	cin >> q;
	vector <Query> qry(q);
	for(i = 0; i < q; i++) {
		cin >> qry[i].type >> qry[i].a >> qry[i].b;
	}

	DSU dsu; dsu.init(n);
	
	vector < vector < pair <int, int> > > G(n + 1);
	vector <int> sol(q + 1), curw(m + 1);
	vector <bool> vis(m + 1);
	vector <int> mark(n + 1);
	int now = 0;

	function <int(int, int)> dfs = [&](int nod, int w) {
		nod = dsu.root(nod);
		if(mark[nod] == now) return 0;
		int ans = dsu.sz[nod];
		mark[nod] = now;
		for(auto it : G[nod]) {
			if(curw[it.second] >= w) {
				ans += dfs(it.first, w);
			}
		}
		return ans;
	};	

	for(i = 0; i < q; i += B) {
		for(j = 1; j <= n; j++) {
			G[j].clear();
			dsu.par[j] = 0, dsu.sz[j] = 1;
		}
		fill(vis.begin(), vis.end(), 0);
		vector <Data> nodes;

		int lim = min(q, i + B);
		for(j = i; j < lim; j++) {
			if(qry[j].type == 1) {
				vis[qry[j].a] = 1;
			}
			else {
				nodes.push_back({qry[j].b, qry[j].a, j});
			}
		}

		vector < pair <int, int> > edges;
		for(j = 1; j <= m; j++) {
			curw[j] = weight[j];
			if(vis[j] == 0) {
				edges.push_back({weight[j], j});
			}
			else {
				G[x[j]].push_back({y[j], j});
				G[y[j]].push_back({x[j], j});
			}
		}

		sort(edges.begin(), edges.end());
		sort(nodes.rbegin(), nodes.rend());

		int pos = (int) edges.size() - 1;
		for(auto &it : nodes) {
			while(pos >= 0 && it.w <= edges[pos].first) {
				int id = edges[pos].second;
				int a = dsu.root(x[id]), b = dsu.root(y[id]);
				if(a != b) {
					if(G[a].size() > G[b].size()) {
						swap(a, b);
					}
					for(auto &it : G[a]) {
						G[b].push_back(it);
					}
					dsu.join(a, b);
				}
				pos--;
			}
			for(j = i; j < it.pos; j++) {
				if(qry[j].type == 1) {
					curw[qry[j].a] = qry[j].b;
				}
			}
			now++;
			sol[it.pos] = dfs(it.nod, it.w);
			for(j = i; j < it.pos; j++) {
				if(qry[j].type == 1) {
					curw[qry[j].a] = weight[qry[j].a];
				}
			}
		}
		
		for(j = i; j < lim; j++) {
			if(qry[j].type == 1) {
				weight[qry[j].a] = qry[j].b;
			}
		}
	}

	for(i = 0; i < q; i++) {
		if(qry[i].type == 2) {
			cout << sol[i] << "\n";
		}
	}
		
	return 0;
}

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 380 KB Output is correct
3 Correct 81 ms 760 KB Output is correct
4 Correct 20 ms 632 KB Output is correct
5 Correct 35 ms 504 KB Output is correct
6 Correct 32 ms 504 KB Output is correct
7 Correct 32 ms 572 KB Output is correct
8 Correct 29 ms 504 KB Output is correct
9 Correct 36 ms 572 KB Output is correct
10 Correct 27 ms 572 KB Output is correct
11 Correct 26 ms 576 KB Output is correct
12 Correct 27 ms 508 KB Output is correct
13 Correct 34 ms 632 KB Output is correct
14 Correct 31 ms 632 KB Output is correct
15 Correct 33 ms 504 KB Output is correct
16 Correct 32 ms 504 KB Output is correct
17 Correct 31 ms 588 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 877 ms 9728 KB Output is correct
2 Correct 880 ms 9572 KB Output is correct
3 Correct 1020 ms 9704 KB Output is correct
4 Correct 934 ms 9812 KB Output is correct
5 Correct 891 ms 9716 KB Output is correct
6 Correct 2597 ms 9792 KB Output is correct
7 Correct 1812 ms 9920 KB Output is correct
8 Correct 1460 ms 9856 KB Output is correct
9 Correct 181 ms 2140 KB Output is correct
10 Correct 2007 ms 9892 KB Output is correct
11 Correct 1630 ms 9748 KB Output is correct
12 Correct 1034 ms 8856 KB Output is correct
13 Correct 981 ms 9956 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 826 ms 8100 KB Output is correct
2 Correct 1427 ms 4096 KB Output is correct
3 Correct 2143 ms 7792 KB Output is correct
4 Correct 1160 ms 7744 KB Output is correct
5 Correct 181 ms 2268 KB Output is correct
6 Correct 1086 ms 7912 KB Output is correct
7 Correct 962 ms 7868 KB Output is correct
8 Correct 837 ms 8136 KB Output is correct
9 Correct 846 ms 6956 KB Output is correct
10 Correct 784 ms 6836 KB Output is correct
11 Correct 718 ms 8192 KB Output is correct
12 Correct 632 ms 8160 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1871 ms 11772 KB Output is correct
2 Correct 181 ms 3448 KB Output is correct
3 Correct 181 ms 7900 KB Output is correct
4 Correct 134 ms 7932 KB Output is correct
5 Correct 1723 ms 14000 KB Output is correct
6 Correct 1865 ms 15576 KB Output is correct
7 Correct 1661 ms 14060 KB Output is correct
8 Correct 836 ms 11232 KB Output is correct
9 Correct 857 ms 11164 KB Output is correct
10 Correct 847 ms 10904 KB Output is correct
11 Correct 1346 ms 13928 KB Output is correct
12 Correct 1342 ms 14060 KB Output is correct
13 Correct 1428 ms 13892 KB Output is correct
14 Correct 1494 ms 14056 KB Output is correct
15 Correct 1597 ms 14084 KB Output is correct
16 Correct 1887 ms 15112 KB Output is correct
17 Correct 1890 ms 14872 KB Output is correct
18 Correct 1803 ms 15208 KB Output is correct
19 Correct 1817 ms 15004 KB Output is correct
20 Correct 1488 ms 14048 KB Output is correct
21 Correct 1501 ms 13960 KB Output is correct
22 Correct 1809 ms 14548 KB Output is correct
23 Correct 1536 ms 12236 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 877 ms 9728 KB Output is correct
2 Correct 880 ms 9572 KB Output is correct
3 Correct 1020 ms 9704 KB Output is correct
4 Correct 934 ms 9812 KB Output is correct
5 Correct 891 ms 9716 KB Output is correct
6 Correct 2597 ms 9792 KB Output is correct
7 Correct 1812 ms 9920 KB Output is correct
8 Correct 1460 ms 9856 KB Output is correct
9 Correct 181 ms 2140 KB Output is correct
10 Correct 2007 ms 9892 KB Output is correct
11 Correct 1630 ms 9748 KB Output is correct
12 Correct 1034 ms 8856 KB Output is correct
13 Correct 981 ms 9956 KB Output is correct
14 Correct 826 ms 8100 KB Output is correct
15 Correct 1427 ms 4096 KB Output is correct
16 Correct 2143 ms 7792 KB Output is correct
17 Correct 1160 ms 7744 KB Output is correct
18 Correct 181 ms 2268 KB Output is correct
19 Correct 1086 ms 7912 KB Output is correct
20 Correct 962 ms 7868 KB Output is correct
21 Correct 837 ms 8136 KB Output is correct
22 Correct 846 ms 6956 KB Output is correct
23 Correct 784 ms 6836 KB Output is correct
24 Correct 718 ms 8192 KB Output is correct
25 Correct 632 ms 8160 KB Output is correct
26 Correct 1190 ms 10520 KB Output is correct
27 Correct 2343 ms 10652 KB Output is correct
28 Correct 1347 ms 10400 KB Output is correct
29 Correct 1033 ms 10380 KB Output is correct
30 Correct 1734 ms 10156 KB Output is correct
31 Correct 1877 ms 10184 KB Output is correct
32 Correct 1902 ms 10236 KB Output is correct
33 Correct 1073 ms 10020 KB Output is correct
34 Correct 1074 ms 10252 KB Output is correct
35 Correct 1105 ms 10280 KB Output is correct
36 Correct 974 ms 9912 KB Output is correct
37 Correct 977 ms 9968 KB Output is correct
38 Correct 1038 ms 10352 KB Output is correct
39 Correct 983 ms 9228 KB Output is correct
40 Correct 1010 ms 9008 KB Output is correct
41 Correct 999 ms 9132 KB Output is correct
42 Correct 789 ms 10216 KB Output is correct
43 Correct 805 ms 10528 KB Output is correct
44 Correct 803 ms 10248 KB Output is correct

Subtask #6
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 380 KB Output is correct
3 Correct 81 ms 760 KB Output is correct
4 Correct 20 ms 632 KB Output is correct
5 Correct 35 ms 504 KB Output is correct
6 Correct 32 ms 504 KB Output is correct
7 Correct 32 ms 572 KB Output is correct
8 Correct 29 ms 504 KB Output is correct
9 Correct 36 ms 572 KB Output is correct
10 Correct 27 ms 572 KB Output is correct
11 Correct 26 ms 576 KB Output is correct
12 Correct 27 ms 508 KB Output is correct
13 Correct 34 ms 632 KB Output is correct
14 Correct 31 ms 632 KB Output is correct
15 Correct 33 ms 504 KB Output is correct
16 Correct 32 ms 504 KB Output is correct
17 Correct 31 ms 588 KB Output is correct
18 Correct 877 ms 9728 KB Output is correct
19 Correct 880 ms 9572 KB Output is correct
20 Correct 1020 ms 9704 KB Output is correct
21 Correct 934 ms 9812 KB Output is correct
22 Correct 891 ms 9716 KB Output is correct
23 Correct 2597 ms 9792 KB Output is correct
24 Correct 1812 ms 9920 KB Output is correct
25 Correct 1460 ms 9856 KB Output is correct
26 Correct 181 ms 2140 KB Output is correct
27 Correct 2007 ms 9892 KB Output is correct
28 Correct 1630 ms 9748 KB Output is correct
29 Correct 1034 ms 8856 KB Output is correct
30 Correct 981 ms 9956 KB Output is correct
31 Correct 826 ms 8100 KB Output is correct
32 Correct 1427 ms 4096 KB Output is correct
33 Correct 2143 ms 7792 KB Output is correct
34 Correct 1160 ms 7744 KB Output is correct
35 Correct 181 ms 2268 KB Output is correct
36 Correct 1086 ms 7912 KB Output is correct
37 Correct 962 ms 7868 KB Output is correct
38 Correct 837 ms 8136 KB Output is correct
39 Correct 846 ms 6956 KB Output is correct
40 Correct 784 ms 6836 KB Output is correct
41 Correct 718 ms 8192 KB Output is correct
42 Correct 632 ms 8160 KB Output is correct
43 Correct 1871 ms 11772 KB Output is correct
44 Correct 181 ms 3448 KB Output is correct
45 Correct 181 ms 7900 KB Output is correct
46 Correct 134 ms 7932 KB Output is correct
47 Correct 1723 ms 14000 KB Output is correct
48 Correct 1865 ms 15576 KB Output is correct
49 Correct 1661 ms 14060 KB Output is correct
50 Correct 836 ms 11232 KB Output is correct
51 Correct 857 ms 11164 KB Output is correct
52 Correct 847 ms 10904 KB Output is correct
53 Correct 1346 ms 13928 KB Output is correct
54 Correct 1342 ms 14060 KB Output is correct
55 Correct 1428 ms 13892 KB Output is correct
56 Correct 1494 ms 14056 KB Output is correct
57 Correct 1597 ms 14084 KB Output is correct
58 Correct 1887 ms 15112 KB Output is correct
59 Correct 1890 ms 14872 KB Output is correct
60 Correct 1803 ms 15208 KB Output is correct
61 Correct 1817 ms 15004 KB Output is correct
62 Correct 1488 ms 14048 KB Output is correct
63 Correct 1501 ms 13960 KB Output is correct
64 Correct 1809 ms 14548 KB Output is correct
65 Correct 1536 ms 12236 KB Output is correct
66 Correct 1190 ms 10520 KB Output is correct
67 Correct 2343 ms 10652 KB Output is correct
68 Correct 1347 ms 10400 KB Output is correct
69 Correct 1033 ms 10380 KB Output is correct
70 Correct 1734 ms 10156 KB Output is correct
71 Correct 1877 ms 10184 KB Output is correct
72 Correct 1902 ms 10236 KB Output is correct
73 Correct 1073 ms 10020 KB Output is correct
74 Correct 1074 ms 10252 KB Output is correct
75 Correct 1105 ms 10280 KB Output is correct
76 Correct 974 ms 9912 KB Output is correct
77 Correct 977 ms 9968 KB Output is correct
78 Correct 1038 ms 10352 KB Output is correct
79 Correct 983 ms 9228 KB Output is correct
80 Correct 1010 ms 9008 KB Output is correct
81 Correct 999 ms 9132 KB Output is correct
82 Correct 789 ms 10216 KB Output is correct
83 Correct 805 ms 10528 KB Output is correct
84 Correct 803 ms 10248 KB Output is correct
85 Correct 2582 ms 17552 KB Output is correct
86 Correct 286 ms 7992 KB Output is correct
87 Correct 249 ms 7948 KB Output is correct
88 Correct 2491 ms 15888 KB Output is correct
89 Correct 2609 ms 17584 KB Output is correct
90 Correct 2459 ms 15636 KB Output is correct
91 Correct 939 ms 12400 KB Output is correct
92 Correct 930 ms 12392 KB Output is correct
93 Correct 951 ms 12276 KB Output is correct
94 Correct 1496 ms 17872 KB Output is correct
95 Correct 1486 ms 17744 KB Output is correct
96 Correct 1566 ms 17932 KB Output is correct
97 Correct 1830 ms 14504 KB Output is correct
98 Correct 1802 ms 16864 KB Output is correct
99 Correct 2497 ms 17484 KB Output is correct
100 Correct 2410 ms 17448 KB Output is correct
101 Correct 2421 ms 17736 KB Output is correct
102 Correct 2231 ms 17704 KB Output is correct
103 Correct 1934 ms 18296 KB Output is correct
104 Correct 1911 ms 18184 KB Output is correct
105 Correct 1508 ms 21292 KB Output is correct
106 Correct 1262 ms 20172 KB Output is correct
107 Correct 1682 ms 14944 KB Output is correct
108 Correct 2849 ms 16972 KB Output is correct
109 Correct 2701 ms 14564 KB Output is correct