Submission #641918

#	Time	Username	Problem	Language	Result	Execution time	Memory
641918		GusterGoose27	다리 (APIO19_bridges)	C++11	13 / 100	330 ms	524288 KiB

bridges

#include <bits/stdc++.h>

using namespace std;

typedef pair<int, int> pii;

const int MAXN = 2e5;
const int MAXM = 2e5;
int n, m, q;

vector<pii> edges[MAXN];
int weights[MAXM];
bool vis[MAXN];

int dfs(int cur, int mxw) {
	if (vis[cur]) return 0;
	int ans = 1;
	vis[cur] = 1;
	for (pii p: edges[cur]) {
		if (vis[p.first] || weights[p.second] < mxw) continue;
		ans += dfs(p.first, mxw);
	}
	return ans;
}

void prog1() {
	for (int i = 0; i < q; i++) {
		int t; cin >> t;
		if (t == 1) {
			int b, r; cin >> b >> r;
			weights[b-1] = r;
		}
		else {
			int s, r; cin >> s >> r;
			s--;
			fill(vis, vis+n, 0);
			cout << dfs(s, r) << "\n";
		}
	}
}

class stree {
public:
	int mn;
	int lp, rp;
	stree *l = nullptr;
	stree *r = nullptr;
	stree(int lv, int rv) {
		lp = lv;
		rp = rv;
		if (lp == rp) {
			mn = weights[lp];
		}
		else {
			int mid = (lp+rp)/2;
			l = new stree(lp, mid);
			r = new stree(mid+1, rp);
			mn = min(l->mn, r->mn);
		}
	}
	void upd(int p, int v) {
		if (lp > p || rp < p) return;
		if (lp == rp) {
			mn = v;
			return;
		}
		l->upd(p, v);
		r->upd(p, v);
		mn = min(l->mn, r->mn);
	}
	int far_left(int p, int v) { // >= p, val < v
		if (rp < p || mn >= v) return n-1;
		if (lp == rp) return lp;
		int lq = l->far_left(p, v);
		if (lq < n-1) return lq;
		return r->far_left(p, v);
	}
	int far_right(int p, int v) { // <= p, val < v
		if (lp > p || mn >= v) return -1;
		if (lp == rp) return lp;
		int rq = r->far_right(p, v);
		if (rq > -1) return rq;
		return l->far_right(p, v);
	}
};

stree *tree;

void prog2() {
	ios_base::sync_with_stdio(false); cin.tie(NULL);
	tree = new stree(0, n-2);
	for (int i = 0; i < q; i++) {
		int t; cin >> t;
		if (t == 2) {
			int s, w; cin >> s >> w; s--;
			int rn = tree->far_left(s, w);
			int ln = tree->far_right(s-1, w);
			cout << (rn-ln) << "\n";
		}
		if (t == 1) {
			int s, w; cin >> s >> w; s--;
			tree->upd(s, w);
		}
	}
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL);
	cin >> n >> m;
	for (int i = 0; i < m; i++) {
		int x, y; cin >> x >> y >> weights[i];
		x--; y--;
		edges[x].push_back(pii(y, i));
		edges[y].push_back(pii(x, i));
	}
	cin >> q;
	if (n <= 1000 && m <= 1000 && q <= 10000) {
		prog1();
		return 0;
	}
	prog2();
}

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