Submission #373742

---

Source Code Expand

#include <string>
#include <vector>
#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <sstream>
#include <algorithm>
#include <cstring>

using namespace std;
typedef long long LL;

#define MAX 1000000000


int edgeId[1001][1001];
int cut[1001][1001];
int edgeA[1001];
int edgeB[1001];
int edgeC[1001];
vector<int> con[1001];

int visited[1001];
int min_edge_value;
int min_edge_id;

void min_search(int current) {
	vector<int> nexts = con[current];

	visited[current] = 1;
	for (int i = 0; i < nexts.size(); i++) {
		int next = nexts[i];
		if (visited[next]) continue;
		if (cut[current][next]) continue;

		int e = edgeId[current][next];
		int d = edgeC[e];
//		cerr << "edgeId: " << e << ", value: " << d << endl;
		if (min_edge_value > d) {
			min_edge_value = d;
			min_edge_id = e;
		} else if (min_edge_value == d) {
			if (min_edge_id > e) {
				min_edge_id = e;
			}
		}
		min_search(next);
	}
}

void query1() {
	int v, d; cin >> v >> d;
	int a = edgeA[v];
	int b = edgeB[v];

	if (cut[a][b]) return;

	edgeC[v] += d;
}
void query2() {
	int v; cin >> v;

	int a = edgeA[v];
	int b = edgeB[v];
	if (cut[a][b]) {
		cout << -1 << endl;
		return;
	}

	min_edge_value = MAX;
	memset(visited, 0, sizeof(visited));
	min_search(a);
	cout << min_edge_id << endl;

	int removeA = edgeA[min_edge_id];
	int removeB = edgeB[min_edge_id];

	cut[removeA][removeB] = 1;
	cut[removeB][removeA] = 1;	
}

int main() {
	int N; cin >> N;
	for (int i = 1; i <= N - 1; i++) {
		int a, b, c; cin >> a >> b >> c;
		con[a].push_back(b);
		con[b].push_back(a);
		edgeA[i] = a;
		edgeB[i] = b;
		edgeC[i] = c;
		edgeId[a][b] = i;
		edgeId[b][a] = i;
	}

	int Q; cin >> Q;
	for (int i = 0; i < Q; i++) {
		int type; cin >> type;
		if (type == 1) {
			query1();
		} else if (type == 2) {
			query2();
		}
	}

	return 0;
}

Submission Info

Judge Result