oj.uz

Submission #140559

# Submission time Handle Problem Language Result Execution time Memory
140559 2019-08-03T14:03:37 Z luciocf Bridges (APIO19_bridges) C++14
43 / 100
 411 ms 6776 KB 
#include <bits/stdc++.h>

using namespace std;

typedef pair<int, int> pii;

const int maxn = 1e5+10;
const int inf = 1e9+10;

struct Edge
{
	int u, v, w;
} edge[maxn], aux[1010];

struct Op
{
	int u, w, ind;
} query[maxn];

int n, m, q;
int tot;

int ans[maxn];

int pai[maxn], peso[maxn];

int tree[4*maxn];

vector<pii> grafo[maxn];

bool comp(Edge a, Edge b) {return a.w > b.w;}
bool comp2(Op a, Op b) {return a.w > b.w;}

void init(void)
{
	for (int i = 1; i <= n; i++)
	{
		pai[i] = i, peso[i] = 1;
		grafo[i].clear();
	}
}

int Find(int x)
{
	if (pai[x] == x) return x;
	return pai[x] = Find(pai[x]);
}

void Join(int x, int y)
{
	x = Find(x), y = Find(y);
	if (x == y) return;

	if (peso[x] < peso[y]) swap(x, y);

	pai[y] = x, peso[x] += peso[y];
}

void get_mst(void)
{
	init();

	for (int i = 1; i <= m; i++)
		aux[i] = edge[i];

	sort(aux+1, aux+m+1, comp);

	for (int i = 1; i <= m; i++)
	{
		if (Find(aux[i].u) != Find(aux[i].v))
		{
			Join(aux[i].u, aux[i].v);

			grafo[aux[i].u].push_back({aux[i].v, aux[i].w});
			grafo[aux[i].v].push_back({aux[i].u, aux[i].w});
		}
	}
}

void dfs(int u, int p, int w)
{
	tot++;

	for (auto v: grafo[u])
		if (v.first != p && v.second >= w)
			dfs(v.first, u, w);
}

void build(int node, int l, int r)
{
	if (l == r)
	{
		tree[node] = edge[l].w;
		return;
	}

	int mid = (l+r)>>1;

	build(2*node, l, mid); build(2*node+1, mid+1, r);

	tree[node] = min(tree[2*node], tree[2*node+1]);
}

void upd(int node, int l, int r, int pos, int v)
{
	if (l == r)
	{
		tree[node] = v;
		return;
	}

	int mid = (l+r)>>1;

	if (pos <= mid) upd(2*node, l, mid, pos, v);
	else upd(2*node+1, mid+1, r, pos, v);

	tree[node] = min(tree[2*node], tree[2*node+1]);
}

int busca1(int node, int l, int r, int pos, int v)
{
	if (tree[node] >= v || r <= pos) return inf;

	if (l == r) return l;

	int mid = (l+r)>>1;

	int p1 = busca1(2*node, l, mid, pos, v);
	if (p1 != inf) return p1;

	return busca1(2*node+1, mid+1, r, pos, v);
}

int busca2(int node, int l, int r, int pos, int v)
{
	if (tree[node] >= v || l >= pos) return inf;

	if (l == r) return l;

	int mid = (l+r)>>1;

	int p1 = busca2(2*node+1, mid+1, r, pos, v);
	if (p1 != inf) return p1;

	return busca2(2*node, l, mid, pos, v);
}

void solve_small(void)
{
	for (int i = 1; i <= q; i++)
	{
		int op;
		scanf("%d", &op);

		if (op == 1)
		{
			int ind, w;
			scanf("%d %d", &ind, &w);

			edge[ind].w = w;
		}
		else
		{
			int u, w;
			scanf("%d %d", &u, &w);

			get_mst();

			tot = 0;
			dfs(u, 0, w);

			printf("%d\n", tot);
		}
	}
}

void solve_chain(void)
{
	if (n > 1)
		build(1, 1, n-1);

	for (int i = 1; i <= q; i++)
	{
		int op;
		scanf("%d", &op);

		if (op == 1)
		{
			int ind, w;
			scanf("%d %d", &ind, &w);

			if (n > 1)
				upd(1, 1, n-1, ind, w);
		}
		else
		{
			int u, w;
			scanf("%d %d", &u, &w);

			if (n == 1)
			{
				printf("1\n");
				continue;
			}

			int r = busca1(1, 1, n-1, u-1, w);
			int l = busca2(1, 1, n-1, u, w);

			int ans = (r == inf ? n-u : r-u);

			ans += (l == inf ? u-1 : u-l-1);

			printf("%d\n", ans+1);
		}
	}
}

void solve_two(void)
{
	for (int i = 1; i <= q; i++)
	{
		int fuckyou;
		scanf("%d", &fuckyou);

		scanf("%d %d", &query[i].u, &query[i].w);
		query[i].ind = i;
	}

	sort(edge+1, edge+m+1, comp);
	sort(query+1, query+q+1, comp2);

	init();

	int p = 1;

	for (int i = 1; i <= q; i++)
	{
		while (edge[p].w >= query[i].w)
		{
			Join(edge[p].u, edge[p].v);
			p++;
		}

		ans[query[i].ind] = peso[Find(query[i].u)];
	}

	for (int i = 1; i <= q; i++)
		printf("%d\n", ans[i]);
}

int main(void)
{
	scanf("%d %d", &n, &m);

	bool ok = 1;
	if (m != n-1) ok = 0;

	for (int i = 1; i <= m; i++)
	{
		int u, v, w;
		scanf("%d %d %d", &u, &v, &w);

		edge[i] = {u, v, w};

		if (v != i+1 || u != i) ok = 0;
	}

	scanf("%d", &q);
	
	if (n <= 1000 && m <= 1000 && q <= 10000)
	{
		solve_small();
		return 0;
	}

	if (ok)
	{
		solve_chain();
		return 0;
	}

	solve_two();
}

Compilation message

bridges.cpp: In function 'void solve_small()':
bridges.cpp:153:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &op);
   ~~~~~^~~~~~~~~~~
bridges.cpp:158:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d %d", &ind, &w);
    ~~~~~^~~~~~~~~~~~~~~~~~~
bridges.cpp:165:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d %d", &u, &w);
    ~~~~~^~~~~~~~~~~~~~~~~
bridges.cpp: In function 'void solve_chain()':
bridges.cpp:185:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &op);
   ~~~~~^~~~~~~~~~~
bridges.cpp:190:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d %d", &ind, &w);
    ~~~~~^~~~~~~~~~~~~~~~~~~
bridges.cpp:198:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d %d", &u, &w);
    ~~~~~^~~~~~~~~~~~~~~~~
bridges.cpp: In function 'void solve_two()':
bridges.cpp:223:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &fuckyou);
   ~~~~~^~~~~~~~~~~~~~~~
bridges.cpp:225:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d", &query[i].u, &query[i].w);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
bridges.cpp: In function 'int main()':
bridges.cpp:253: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:261:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d %d", &u, &v, &w);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
bridges.cpp:268:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &q);
  ~~~~~^~~~~~~~~~

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2680 KB Output is correct
2 Correct 4 ms 2680 KB Output is correct
3 Correct 411 ms 2936 KB Output is correct
4 Correct 9 ms 2680 KB Output is correct
5 Correct 31 ms 2680 KB Output is correct
6 Correct 25 ms 2680 KB Output is correct
7 Correct 36 ms 2680 KB Output is correct
8 Correct 44 ms 2808 KB Output is correct
9 Correct 39 ms 2680 KB Output is correct
10 Correct 42 ms 2680 KB Output is correct
11 Correct 42 ms 2740 KB Output is correct
12 Correct 42 ms 2680 KB Output is correct
13 Correct 63 ms 2652 KB Output is correct
14 Correct 62 ms 2808 KB Output is correct
15 Correct 67 ms 2808 KB Output is correct
16 Correct 34 ms 2680 KB Output is correct
17 Correct 36 ms 2680 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 104 ms 3888 KB Output is correct
2 Correct 101 ms 4012 KB Output is correct
3 Correct 102 ms 3932 KB Output is correct
4 Correct 97 ms 3828 KB Output is correct
5 Correct 100 ms 3832 KB Output is correct
6 Correct 88 ms 4192 KB Output is correct
7 Correct 89 ms 4088 KB Output is correct
8 Correct 91 ms 3960 KB Output is correct
9 Correct 43 ms 4216 KB Output is correct
10 Correct 75 ms 5624 KB Output is correct
11 Correct 78 ms 5624 KB Output is correct
12 Correct 96 ms 6776 KB Output is correct
13 Correct 84 ms 6520 KB Output is correct

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 83 ms 5180 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 125 ms 6252 KB Output is correct
2 Correct 42 ms 3064 KB Output is correct
3 Correct 59 ms 4216 KB Output is correct
4 Correct 47 ms 4160 KB Output is correct
5 Correct 92 ms 6656 KB Output is correct
6 Correct 123 ms 6392 KB Output is correct
7 Correct 91 ms 6392 KB Output is correct
8 Correct 94 ms 5624 KB Output is correct
9 Correct 94 ms 5536 KB Output is correct
10 Correct 94 ms 5880 KB Output is correct
11 Correct 109 ms 5960 KB Output is correct
12 Correct 109 ms 5880 KB Output is correct
13 Correct 108 ms 6136 KB Output is correct
14 Correct 92 ms 6520 KB Output is correct
15 Correct 91 ms 6520 KB Output is correct
16 Correct 123 ms 6364 KB Output is correct
17 Correct 124 ms 6264 KB Output is correct
18 Correct 124 ms 6404 KB Output is correct
19 Correct 124 ms 6404 KB Output is correct
20 Correct 114 ms 6256 KB Output is correct
21 Correct 112 ms 6276 KB Output is correct
22 Correct 119 ms 6520 KB Output is correct
23 Correct 86 ms 6240 KB Output is correct

Subtask #5
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 104 ms 3888 KB Output is correct
2 Correct 101 ms 4012 KB Output is correct
3 Correct 102 ms 3932 KB Output is correct
4 Correct 97 ms 3828 KB Output is correct
5 Correct 100 ms 3832 KB Output is correct
6 Correct 88 ms 4192 KB Output is correct
7 Correct 89 ms 4088 KB Output is correct
8 Correct 91 ms 3960 KB Output is correct
9 Correct 43 ms 4216 KB Output is correct
10 Correct 75 ms 5624 KB Output is correct
11 Correct 78 ms 5624 KB Output is correct
12 Correct 96 ms 6776 KB Output is correct
13 Correct 84 ms 6520 KB Output is correct
14 Incorrect 83 ms 5180 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2680 KB Output is correct
2 Correct 4 ms 2680 KB Output is correct
3 Correct 411 ms 2936 KB Output is correct
4 Correct 9 ms 2680 KB Output is correct
5 Correct 31 ms 2680 KB Output is correct
6 Correct 25 ms 2680 KB Output is correct
7 Correct 36 ms 2680 KB Output is correct
8 Correct 44 ms 2808 KB Output is correct
9 Correct 39 ms 2680 KB Output is correct
10 Correct 42 ms 2680 KB Output is correct
11 Correct 42 ms 2740 KB Output is correct
12 Correct 42 ms 2680 KB Output is correct
13 Correct 63 ms 2652 KB Output is correct
14 Correct 62 ms 2808 KB Output is correct
15 Correct 67 ms 2808 KB Output is correct
16 Correct 34 ms 2680 KB Output is correct
17 Correct 36 ms 2680 KB Output is correct
18 Correct 104 ms 3888 KB Output is correct
19 Correct 101 ms 4012 KB Output is correct
20 Correct 102 ms 3932 KB Output is correct
21 Correct 97 ms 3828 KB Output is correct
22 Correct 100 ms 3832 KB Output is correct
23 Correct 88 ms 4192 KB Output is correct
24 Correct 89 ms 4088 KB Output is correct
25 Correct 91 ms 3960 KB Output is correct
26 Correct 43 ms 4216 KB Output is correct
27 Correct 75 ms 5624 KB Output is correct
28 Correct 78 ms 5624 KB Output is correct
29 Correct 96 ms 6776 KB Output is correct
30 Correct 84 ms 6520 KB Output is correct
31 Incorrect 83 ms 5180 KB Output isn't correct
32 Halted 0 ms 0 KB -