oj.uz

Submission #333174

# Submission time Handle Problem Language Result Execution time Memory
333174 2020-12-04T21:23:30 Z limabeans Toll (BOI17_toll) C++17
7 / 100
 28 ms 4844 KB 
#include <bits/stdc++.h>
using namespace std;

template<typename T>
void out(T x) { cout << x << endl; exit(0); }
#define watch(x) cout << (#x) << " is " << (x) << endl





using ll = long long;


struct dsu0 {
    vector<int> par, siz;
    int n;
    int cc;
    int largest;
    void init(int n) {
	assert(n>0);
	this->n=n;
	cc=n;
	par.resize(n+10);siz.resize(n+10);
	for (int i=0; i<n; i++) par[i]=i,siz[i]=1;
	largest=1;
    }
    int parent(int x) {
	assert(x>=0 && x<n);
	return par[x]==x?x:par[x]=parent(par[x]);
    }
    bool join(int x, int y) {
	x=parent(x);y=parent(y);
	if (x==y) return false;
	cc--;
	if (siz[x]<siz[y]) swap(x,y);
	siz[x]+=siz[y];par[y]=x;
	largest=max(largest,siz[x]);
	return true;
    }
};

const int maxn = 5e4+10;

int k,n,m,o;
vector<pair<ll,int>> g[maxn];

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0);  cout.tie(0);

    cin>>k>>n>>m>>o;
    assert(k==1);


    dsu0 dsu;
    dsu.init(n);

    vector<ll> pre(n,0);

    for (int i=0; i<m; i++) {
	int u,v; cin>>u>>v;
	dsu.join(u,v);
	int w; cin>>w;
	pre[u]+=w;
	g[u].push_back({w,v});
    }

    for (int i=1; i<n; i++) {
	pre[i] += pre[i-1];
    }

    while (o--) {
	int u,v;
	cin>>u>>v;
	if (dsu.parent(u)!=dsu.parent(v)) {
	    cout<<"-1\n";
	    continue;
	}
	ll res = pre[v-1]-(u==0?0:pre[u-1]);
	cout<<res<<"\n";	    
    }
    
    
    return 0;
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 4844 KB Output is correct
2 Correct 1 ms 1516 KB Output is correct
3 Correct 1 ms 1516 KB Output is correct
4 Correct 1 ms 1516 KB Output is correct
5 Correct 2 ms 1516 KB Output is correct
6 Correct 2 ms 1516 KB Output is correct
7 Correct 2 ms 1516 KB Output is correct
8 Correct 27 ms 4844 KB Output is correct
9 Correct 28 ms 4844 KB Output is correct
10 Correct 4 ms 2412 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 4 ms 2924 KB Execution killed with signal 6 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1516 KB Output is correct
2 Runtime error 3 ms 2924 KB Execution killed with signal 6 (could be triggered by violating memory limits)
3 Halted 0 ms 0 KB -

Subtask #4
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1516 KB Output is correct
2 Runtime error 3 ms 2924 KB Execution killed with signal 6 (could be triggered by violating memory limits)
3 Halted 0 ms 0 KB -

Subtask #5
0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 4844 KB Output is correct
2 Correct 1 ms 1516 KB Output is correct
3 Correct 1 ms 1516 KB Output is correct
4 Correct 1 ms 1516 KB Output is correct
5 Correct 2 ms 1516 KB Output is correct
6 Correct 2 ms 1516 KB Output is correct
7 Correct 2 ms 1516 KB Output is correct
8 Correct 27 ms 4844 KB Output is correct
9 Correct 28 ms 4844 KB Output is correct
10 Correct 4 ms 2412 KB Output is correct
11 Runtime error 4 ms 2924 KB Execution killed with signal 6 (could be triggered by violating memory limits)
12 Halted 0 ms 0 KB -