Submission #209233

#	Time	Username	Problem	Language	Result	Execution time	Memory
209233		mieszko11b	Bridges (APIO19_bridges)	C++14	16 / 100	418 ms	6776 KiB

bridges

#include <bits/stdc++.h>

using namespace std;

using ii = pair<int, int>;

#define X first
#define Y second

int n, m;
vector<ii> G[50007];
int c[50007];
bool vis[50007];
int cnt;
int d[1200007];
int lv;

void insert(int w, int x) {
	w += lv;
	d[w] = x;
	w /= 2;
	while(w) {
		d[w] = min(d[2 * w], d[2 * w + 1]);
		w /= 2;
	}
}

int qquery(int a, int b) {
	if(a > b) return 1e9;
	int va = a +lv;
	int vb = b + lv;
	int res = min(d[va], d[vb]);
	while(va / 2 != vb/  2) {
		if(va % 2 == 0)
			res = min(res, d[va + 1]);
		if(vb % 2 == 1)
			res = min(res, d[vb - 1]);
		va /= 2;
		vb /= 2;
	}
	return res;
}

void dfs(int w, int lim) {
	if(vis[w]) return;
	vis[w] = 1;
	cnt++;
	
	for(ii u : G[w])
		if(c[u.Y] >= lim)	
			dfs(u.X, lim);
}

int query(int w, int lim) {
	cnt  =0;
	memset(vis, 0, sizeof vis);
	dfs(w, lim);
	return cnt;
}



void update(int i, int v) {
	c[i] = v;
}

void update2(int i, int v) {
	insert(i, v);
}

int query2(int w, int lim) {
	int res = 1;
	int pocz = 0, kon = n - w, mid;
	while(pocz < kon) {
		mid = (pocz + kon + 1) / 2;
		if(qquery(w, w + mid - 1) >= lim)
			pocz = mid;
		else
			kon = mid - 1;
	}
	res += pocz;
	//~ cout << res << endl;
	
	pocz = 0, kon = w - 1;
	while(pocz < kon) {
		mid = (pocz + kon + 1) / 2;
		if(qquery(w - mid, w - 1) >= lim)
			pocz = mid;
		else
			kon = mid - 1;
	}
	res += pocz;
	
	
	return res;
}

int main() {
	scanf("%d%d", &n, &m);
		
	for(int i = 1 ; i <= m ; i++) {
		int a,b, c;
		scanf("%d%d%d", &a, &b, &c);
		G[a].push_back({b, i});
		G[b].push_back({a, i});
		::c[i] = c;
	}
	
	int q;
	scanf("%d", &q);
	
	//~ if(n <= 1000 && m <= 1000 && q <= 10000) {
		//~ while(q--) {
			//~ int t, a, b;
			//~ scanf("%d%d%d", &t, &a, &b);
			//~ if(t == 1)
				//~ update(a, b);
			//~ else
				//~ printf("%d\n", query(a, b));
		//~ }
		//~ return 0;
	//~ }
	
	lv = 2;
	while(lv < n + 2)
		lv *= 2;
		
	for(int i = 1 ; i < n ; i++)
		d[lv + i] = c[i];
	
	for(int i = lv - 1 ; i >= 1 ; i--)
		d[i] = min(d[2 * i], d[2 * i + 1]);

	while(q--) {
		int t, a, b;
		scanf("%d%d%d", &t, &a, &b);
		if(t == 1)
			update2(a, b);
		else
			printf("%d\n", query2(a, b));
	}
	
	return 0;
}

Compilation message (stderr)

bridges.cpp: In function 'int main()':
bridges.cpp:99: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:103:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d%d", &a, &b, &c);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~
bridges.cpp:110:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &q);
  ~~~~~^~~~~~~~~~
bridges.cpp:136:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d%d", &t, &a, &b);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 13
• Subtask 2: 16 / 16
• Subtask 3: 0 / 17
• Subtask 4: 0 / 14
• Subtask 5: 0 / 13
• Subtask 6: 0 / 27