oj.uz

답안 #572454

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
572454 2022-06-04T12:15:25 Z CpDark 다리 (APIO19_bridges) C++14
16 / 100
 411 ms 14176 KB 
#include <bits/stdc++.h>
#define fastInput ios::sync_with_stdio(false); cin.tie(nullptr);

using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef pair<ll, ll> pii;
typedef vector<pii> vp;
typedef vector<bool> vb;
typedef vector<vb> vvb;


struct segmentTree {
	vi st;
	int size;

	void init(int n) {
		for (size = 1; size < n; size *= 2) {}
		st.resize(2 * size);
	}

	void update(int index, int val) {
		index += size;
		st[index] = val;
		for (index /= 2; index; index /= 2) {
			st[index] = min(st[index * 2], st[index * 2 + 1]);
		}
	}

	int query(int l, int r) {
		int ans = INT_MAX;
		for (l += size, r += size; l <= r; l /= 2, r /= 2) {
			if (l % 2) {
				ans = min(ans, st[l]);
				l++;
			}
			if (r % 2 == 0) {
				ans = min(ans, st[r]);
				r--;
			}
		}
		return ans;
	}

};

vector<vp> graph;
vll weight;

vb visited;
segmentTree st;

int lastTrue(int s,int k, int lo, int hi) {
	lo--;
	while (lo < hi) {
		int mid = lo + (hi - lo + 1) / 2;
		bool curr = k <= st.query(s, mid);
		if (curr) {
			lo = mid;
		}
		else {
			hi = mid - 1;
		}
	}
	return lo;
}


int firstTrue(int s, int k, int lo, int hi) {
	hi++;
	while (lo < hi) {
		int mid = lo + (hi - lo) / 2;
		bool curr = k <= st.query(mid, s);

		if (curr) {
			hi = mid;
		}
		else {
			lo = mid + 1;
		}
	}
	return lo;
}


inline int findAmount(int root, int k, int n) {
	int ans = 1;
	int left = lastTrue(root, k, root, n - 1);
	ans += left - root + 1;
	int right = firstTrue(root - 1, k, 1, root - 1);
	ans += root - 1 - right + 1;
	return ans;

}

void dfs(int v, int k) {
	visited[v] = true;
	for (int i = 0; i < graph[v].size(); i++) {
		int u = graph[v][i].first;
		ll w = weight[graph[v][i].second];
		if (k <= w && !visited[u]) {
			dfs(u, k);
		}
	}
}

int main() {
	fastInput;
	int n, m;
	cin >> n >> m;

	st.init(n);
	graph.resize(n + 1);
	weight.resize(m + 1);
	int a, b, d;
	for (int i = 1; i <= m; i++) {
		cin >> a >> b >> d;
		graph[a].push_back({ b,i });
		graph[b].push_back({ a,i });
		weight[i] = d;
		st.update(i, d);
	}


	int q;
	cin >> q;
	int t;
	for (int i = 0; i < q; i++) {
		cin >> t;
		if (t == 1) {
			 int r;
			 cin >> b >> r;
			 weight[b] = r;
			 st.update(b, weight[b]);
		}
		else {
			int s, w;
			cin >> s >> w;
			int ans = findAmount(s, w, n);
			cout << ans << endl;
		}
	}


	return 0;
}

Compilation message

bridges.cpp: In function 'void dfs(int, int)':
bridges.cpp:101:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  101 |  for (int i = 0; i < graph[v].size(); i++) {
      |                  ~~^~~~~~~~~~~~~~~~~

Subtask #1
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
16.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 219 ms 7624 KB Output is correct
2 Correct 189 ms 7592 KB Output is correct
3 Correct 205 ms 7460 KB Output is correct
4 Correct 200 ms 7580 KB Output is correct
5 Correct 202 ms 7596 KB Output is correct
6 Correct 276 ms 7532 KB Output is correct
7 Correct 250 ms 7524 KB Output is correct
8 Correct 237 ms 7572 KB Output is correct
9 Correct 144 ms 1764 KB Output is correct
10 Correct 213 ms 6524 KB Output is correct
11 Correct 208 ms 6500 KB Output is correct
12 Correct 411 ms 7756 KB Output is correct
13 Correct 87 ms 7464 KB Output is correct

Subtask #3
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 190 ms 5824 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 45 ms 14176 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #5
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 219 ms 7624 KB Output is correct
2 Correct 189 ms 7592 KB Output is correct
3 Correct 205 ms 7460 KB Output is correct
4 Correct 200 ms 7580 KB Output is correct
5 Correct 202 ms 7596 KB Output is correct
6 Correct 276 ms 7532 KB Output is correct
7 Correct 250 ms 7524 KB Output is correct
8 Correct 237 ms 7572 KB Output is correct
9 Correct 144 ms 1764 KB Output is correct
10 Correct 213 ms 6524 KB Output is correct
11 Correct 208 ms 6500 KB Output is correct
12 Correct 411 ms 7756 KB Output is correct
13 Correct 87 ms 7464 KB Output is correct
14 Incorrect 190 ms 5824 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -