oj.uz

Submission #333183

# Submission time Handle Problem Language Result Execution time Memory
333183 2020-12-04T21:47:51 Z limabeans Toll (BOI17_toll) C++17
8 / 100
 2381 ms 524292 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;
const ll inf = 1e18;

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];




map<int,ll> dp[maxn];

ll f(int u, int v) {
    if (u==v) return 0;
    
    if (dp[u].count(v)) return dp[u][v];
    ll res = inf;
    for (auto ed: g[u]) {
	res = min(res, ed.first+f(ed.second,v));
    }

    return dp[u][v] = res;
}

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

    cin>>k>>n>>m>>o;



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




    while (o--) {
	int u,v;
	cin>>u>>v;
	ll res = f(u,v);
	if (res>inf/2) res=-1;
	cout<<res<<"\n";
    }
    
    
    return 0;
}

Subtask #1
0 / 7.0

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

Subtask #2
0 / 10.0

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

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 3820 KB Output is correct
2 Correct 3 ms 3840 KB Output is correct
3 Correct 3 ms 3820 KB Output is correct
4 Correct 4 ms 3820 KB Output is correct
5 Correct 3 ms 3820 KB Output is correct
6 Correct 4 ms 4076 KB Output is correct
7 Correct 15 ms 7788 KB Output is correct
8 Correct 25 ms 7916 KB Output is correct
9 Correct 19 ms 7916 KB Output is correct
10 Correct 38 ms 12780 KB Output is correct
11 Correct 1149 ms 229996 KB Output is correct
12 Correct 1093 ms 203908 KB Output is correct
13 Correct 1323 ms 223680 KB Output is correct
14 Correct 1132 ms 215028 KB Output is correct
15 Correct 697 ms 129132 KB Output is correct
16 Correct 663 ms 123116 KB Output is correct

Subtask #4
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 3820 KB Output is correct
2 Correct 3 ms 3840 KB Output is correct
3 Correct 3 ms 3820 KB Output is correct
4 Correct 4 ms 3820 KB Output is correct
5 Correct 3 ms 3820 KB Output is correct
6 Correct 4 ms 4076 KB Output is correct
7 Correct 15 ms 7788 KB Output is correct
8 Correct 25 ms 7916 KB Output is correct
9 Correct 19 ms 7916 KB Output is correct
10 Correct 38 ms 12780 KB Output is correct
11 Correct 1149 ms 229996 KB Output is correct
12 Correct 1093 ms 203908 KB Output is correct
13 Correct 1323 ms 223680 KB Output is correct
14 Correct 1132 ms 215028 KB Output is correct
15 Correct 697 ms 129132 KB Output is correct
16 Correct 663 ms 123116 KB Output is correct
17 Runtime error 2381 ms 524292 KB Execution killed with signal 9 (could be triggered by violating memory limits)
18 Halted 0 ms 0 KB -

Subtask #5
0 / 44.0

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