oj.uz

Submission #249135

# Submission time Handle Problem Language Result Execution time Memory
249135 2020-07-14T12:09:17 Z crossing0ver Bridges (APIO19_bridges) C++17
13 / 100
 3000 ms 7292 KB 
#include<bits/stdc++.h>
#define pb push_back
using namespace std;
const int N = 5e4+5;
struct bridge{
	int a,b,val;
	bridge(){
		a = b = val = 0;
	}
};
int n,m,q;
bool vis[N];
vector<bridge> e;
vector< pair<int,int> > adj[N];
int dfs(int v,int val) {
	int cnt = 1;
	vis[v] = 1;
	for (auto i : adj[v]) {
		if (i.second >= val && !vis[i.first])
			cnt += dfs(i.first,val);
	}
	return cnt;
}
int arr[100009],t[400009];

void build(int v,int tl,int tr) {
	if (tl == tr) {
		t[v] = arr[tl];
		return;
	}
	int tm = (tl + tr)/2;
	build(v*2,tl,tm);
	build(v*2|1,tm+1,tr);
	t[v] = min(t[v*2],t[v*2+1]);
}
void upd(int v,int tl,int tr,int pos,int val) {
	if (tl == tr) {
		t[v] = arr[tl] = val;
		return;
	}
	int tm = (tl + tr)/2;
	if (pos <= tm)
		upd(v*2,tl,tm,pos,val);
	else 
		upd(v*2|1,tm+1,tr,pos,val);
	t[v] = min(t[v*2],t[v*2+1]);
}
int get(int v,int tl,int tr,int l,int r) {
	if (l > tr || r < tl) return INT_MAX;
	if (l <= tl && r >= tr) return t[v];
	int tm = (tl + tr)/2;
	return min( get(v*2,tl,tm,l,r),
				get(v*2|1,tm+1,tr,l,r));
}
void LINE() {
	for (int i = 1; i <= m; i++) {
		arr[i] = e[i].val;
	}
	build(1,1,m);
	for (int type,x,y;q--;) {
		cin >> type >> x >> y;
		if (type == 1) {
			upd(1,1,m,x,y);
		}
		else {
		//	cout << dfs(x,y) <<'\n';
			int lo = x-1, hi = m;
			while (lo < hi) {
				int mid = (lo + hi + 1)/2;
				if (get(1,1,m,x,mid) >= y)
					lo = mid;
				else hi = mid-1;
			} 
			int ans = 1;
			ans = lo + 1 - x;
			lo = 0, hi = x-1;
			while (lo < hi) {
				int mid = (lo + hi)/2;
				if (get(1,1,m,mid,x-1) >= y)
					hi = mid;
				else lo = mid+1;
			}
			if (hi == 0 || get(1,1,m,x,hi) < y) hi++;
			ans += x - hi;
			cout << ans <<'\n';
		}
	}
	
	
	exit(0);
}
main() {
	cin >> n >> m;
	e.resize(m+1);
	bool fl1 = (m == n-1);
	for (int i = 1; i <= m; i++) {
		cin >> e[i].a >> e[i].b >> e[i].val;
		if (e[i].a != i || e[i].b != i+1)
			fl1 = 0;
		adj[e[i].a].pb({e[i].b,e[i].val});
		adj[e[i].b].pb({e[i].a,e[i].val});
	}
	cin >> q;
	if (fl1 && n > 1) {
		LINE();
	}
	
	for (int type,x,y;q--;) {
		cin >> type >> x >> y;
		if (type == 1) {
			int a = e[x].a, b = e[x].b,val = e[x].val;
			adj[a].erase(find(adj[a].begin(),adj[a].end(),make_pair(b,val)));
			adj[b].erase(find(adj[b].begin(),adj[b].end(),make_pair(a,val)));
			e[x].val = y;
			adj[a].pb({b,y});
			adj[b].pb({a,y});
		}
		else {
			cout << dfs(x,y) <<'\n';
			fill(vis,vis+n+1,0);
		}
	}
	
}

Compilation message

bridges.cpp:92:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main() {
      ^

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1536 KB Output is correct
2 Correct 2 ms 1536 KB Output is correct
3 Correct 76 ms 1664 KB Output is correct
4 Correct 38 ms 1712 KB Output is correct
5 Correct 28 ms 1664 KB Output is correct
6 Correct 26 ms 1664 KB Output is correct
7 Correct 24 ms 1536 KB Output is correct
8 Correct 25 ms 1664 KB Output is correct
9 Correct 26 ms 1536 KB Output is correct
10 Correct 24 ms 1664 KB Output is correct
11 Correct 23 ms 1664 KB Output is correct
12 Correct 32 ms 1664 KB Output is correct
13 Correct 27 ms 1664 KB Output is correct
14 Correct 25 ms 1664 KB Output is correct
15 Correct 38 ms 1664 KB Output is correct
16 Correct 23 ms 1536 KB Output is correct
17 Correct 22 ms 1536 KB Output is correct

Subtask #2
0 / 16.0

# Verdict Execution time Memory Grader output
1 Incorrect 694 ms 4580 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2131 ms 3416 KB Output is correct
2 Execution timed out 3046 ms 2136 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

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

Subtask #5
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 694 ms 4580 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1536 KB Output is correct
2 Correct 2 ms 1536 KB Output is correct
3 Correct 76 ms 1664 KB Output is correct
4 Correct 38 ms 1712 KB Output is correct
5 Correct 28 ms 1664 KB Output is correct
6 Correct 26 ms 1664 KB Output is correct
7 Correct 24 ms 1536 KB Output is correct
8 Correct 25 ms 1664 KB Output is correct
9 Correct 26 ms 1536 KB Output is correct
10 Correct 24 ms 1664 KB Output is correct
11 Correct 23 ms 1664 KB Output is correct
12 Correct 32 ms 1664 KB Output is correct
13 Correct 27 ms 1664 KB Output is correct
14 Correct 25 ms 1664 KB Output is correct
15 Correct 38 ms 1664 KB Output is correct
16 Correct 23 ms 1536 KB Output is correct
17 Correct 22 ms 1536 KB Output is correct
18 Incorrect 694 ms 4580 KB Output isn't correct
19 Halted 0 ms 0 KB -