QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#402187#7103. Red Black TreemiaokxRE 0ms0kbC++203.3kb2024-04-30 06:20:492024-04-30 06:20:50

Judging History

你现在查看的是最新测评结果

  • [2024-04-30 06:20:50]
  • 评测
  • 测评结果:RE
  • 用时:0ms
  • 内存:0kb
  • [2024-04-30 06:20:49]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;

vector<long long> cost, d;
vector<bool> red;

vector<vector<int>> adj;
vector<vector<pair<int, int>>> adj2;

// using LCA------------------------------------------------

#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;

template<class T>
struct RMQ {
	vector<vector<T>> jmp;
	RMQ(const vector<T>& V) : jmp(1, V) {
		for (int pw = 1, k = 1; pw * 2 <= sz(V); pw *= 2, ++k) {
			jmp.emplace_back(sz(V) - pw * 2 + 1);
			rep(j,0,sz(jmp[k]))
				jmp[k][j] = min(jmp[k - 1][j], jmp[k - 1][j + pw]);
		}
	}
	T query(int a, int b) {
		assert(a < b); // or return inf if a == b
		int dep = 31 - __builtin_clz(b - a);
		return min(jmp[dep][a], jmp[dep][b - (1 << dep)]);
	}
};

struct LCA {
	int T = 0;
	vi time, path, ret;
	RMQ<int> rmq;

	LCA(vector<vi>& C) : time(sz(C)), rmq((dfs(C,0,-1), ret)) {}
	void dfs(vector<vi>& C, int v, int par) {
		time[v] = T++;
		for (int y : C[v]) if (y != par) {
			path.push_back(v), ret.push_back(time[v]);
			dfs(C, y, v);
		}
	}

	int lca(int a, int b) {
		if (a == b) return a;
		tie(a, b) = minmax(time[a], time[b]);
		return path[rmq.query(a, b)];
	}
	//dist(a,b){return depth[a] + depth[b] - 2*depth[lca(a,b)];}
};

// ---------------------------------------------------------------

void dfs(int cur, int par) {
    for (auto[v, w] : adj2[cur]) {
        if (v == par) continue;
        d[v] = d[cur] + w;
        if (!red[v]) {
            cost[v] = cost[cur] + w;
        }
        dfs(v, cur);
    }
}

void solve() {
    int n, r, q;
    cin >> n >> r >> q;

    adj.assign(n, vector<int>());
    adj2.assign(n, vector<pair<int,int>>());

    cost.assign(n, 0);
    d.assign(n, 0);
    red.assign(n, false);

    for (int i = 0; i < r; i++) {
        int x;
        cin >> x;
        x--;
        red[x] = true;
    }

    for (int i = 0; i < n-1; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        u--;
        v--;
        adj[u].push_back(v);
        adj[v].push_back(u);
        adj2[u].push_back({v, w});
        adj2[v].push_back({u, w});
    }

    dfs(0, -1);

/*
    for (int i = 0; i < n; i++) {
        cout << cost[i] << " \n"[i==n-1];
    }

    for (int i = 0; i < n; i++) {
        cout << d[i] << " \n"[i==n-1];
    }
*/

    LCA lca(adj);

    for (int i = 0; i < q; i++) {
        int k;
        cin >> k;

        vector<int> query(k);
        for (int j = 0; j < k; j++) {
            cin >> query[j];
            query[j]--;
        }

        sort(begin(query), end(query),
        [&](int i, int j) {
            return cost[i] > cost[j];
        });

        int node = query[0];
        long long mxd = d[query[0]];
        long long ans = cost[query[1]];

        for (int i = 1; i + 1 < k; i++) {
            node = lca.lca(node, query[i]);
            mxd = max(mxd, d[query[i]]);
            ans = min(ans, max(mxd - d[node], cost[query[i+1]]));
        }

        cout << ans << '\n';
    }
    adj.clear();
    adj2.clear();
    cost.clear();
    d.clear();
    red.clear();
}

int main() {
    int t;
    cin >> t;
    while (t--)
        solve();
}

详细

Test #1:

score: 0
Runtime Error

input:

2
12 2 4
1 9
1 2 1
2 3 4
3 4 3
3 5 2
2 6 2
6 7 1
6 8 2
2 9 5
9 10 2
9 11 3
1 12 10
3 3 7 8
4 4 5 7 8
4 7 8 10 11
3 4 5 12
3 2 3
1 2
1 2 1
1 3 1
1 1
2 1 2
3 1 2 3

output:

4
5
3
8

result: