QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#64975#5102. Dungeon Crawlervisho33WA 1ms3536kbC++142.9kb2022-11-26 08:34:322022-11-26 08:34:33

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-11-26 08:34:33]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3536kb
  • [2022-11-26 08:34:32]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> ii;
vector<vector<ii>> edges;
vector<int> log1;

struct Tree{
	
	int n;
	int root;
	vector<int> first1;
	vector<int> vis;
	vector<int> euiler;
	vector<int> old_ind;
	vector<int> d;
	vector<vector<int> > v;
	
	void dfsxd(int i, int par){
    	int new_ind = old_ind.size();
    	old_ind.push_back(i);
    	first1[i] = euiler.size();
    	euiler.push_back(new_ind);
    	for(auto x: edges[i]){
    		if(x.first != par){
    			dfsxd(x.first, i);
			}
        	euiler.push_back(new_ind);
    	}
    	return;
	}
	
	void sparse(int n){
    	int p=log1[n];
    	vector<int> v1(n+1,0);
    	for(int i=0;i<=p;i++) v.push_back(v1);
    	for(int i=1;i<=n;i++){
        	v[0][i]=euiler[i];
    	}
    	for(int j=1;j<=p;j++){
        	int len=(1<<j);
        	int len1=len/2;
        	for(int i=1;i+len-1<=n;i++){
            	v[j][i]=min(v[j-1][i],v[j-1][i+len1]);
        	}
    	}
    	
    	return;
	}
	
	void dfs(int v, int p){
    	for(auto u : edges[v]){
        	if(u.first != p){
            	d[u.first] = d[v] + u.second;
            	dfs(u.first, v);
        	}
    	}
    	return;
	}
	
public:
	
    Tree(int nx, int rootx){
        n = nx;
        root = rootx;
        first1.resize(n);
		vis.resize(n);
		d.resize(n);
        dfsxd(root, -1);
        sparse(euiler.size());
        dfs(root, -1);
    }
	
	int query(int a, int b){
		int l = first1[a];
		int r = first1[b];
		if(l>r){
            swap(l, r);
        }
    	int len=r-l+1;
    	int p=log1[len];
    	return min(v[p][l],v[p][r+1-(1<<p)]);
	}
	
};

int main() {

    ios::sync_with_stdio(false);
    cin.tie(NULL);
    
    log1.resize(1005);
    for(int i = 2; i<1005; i++){
        log1[i] = 1 + log1[i/2];
    }

    int n, q;
    cin >> n >> q;

    ll sum = 0;
    edges.resize(n);
    for (int i = 0; i < n - 1; i++) {
        int a, b;
        ll w;
        cin >> a >> b >> w;
        a--;
        b--;
        edges[a].push_back(ii(b, w));
        edges[b].push_back(ii(a, w));
        sum = sum + 2LL * w;
    }

    vector<Tree> tree;
    for(int i = 0; i<n; i++){
    	tree.push_back(Tree(n, i));
	}
	
	vector<int> hojas;
	for(int i = 0; i<n; i++){
		if(edges[i].size() == 1){
			hojas.push_back(i);
		}
	}

    while (q--) {
    	
        int s, k, t;
        cin >> s >> k >> t;
        s--;
        k--;
        t--;
        
        if (tree[s].d[t] + tree[t].d[k] == tree[s].d[k]) {
            cout << "impossible\n";
            continue;
        }
        
        ll diff = 0;
        for(auto u: hojas){
        	int lca1 = tree[k].query(u, t);
        	int lca2 = tree[u].query(t, u);
            diff = max(diff, tree[s].d[u] - 2LL*tree[lca1].d[lca2]);
        }

        cout << sum - diff << "\n";
    }

    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Wrong Answer
time: 1ms
memory: 3536kb

input:

22 5
1 2 7
2 3 5
3 4 8
3 6 6
3 7 3
2 5 6
5 8 2
8 9 11
2 10 16
1 11 12
11 12 4
11 13 9
1 14 25
14 15 4
15 16 5
15 17 6
15 18 1
15 19 8
14 20 7
20 21 9
20 22 17
1 19 9
1 9 19
1 8 9
1 9 8
2 22 11

output:

305
316
293
impossible
286

result:

wrong answer 1st lines differ - expected: '316', found: '305'