oj.uz

Submission #405872

# Submission time Handle Problem Language Result Execution time Memory
405872 2021-05-17T01:31:42 Z thomas_li Toll (BOI17_toll) C++17
7 / 100
 3000 ms 12564 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pi;
const int MM = 5e4+5;
int n,o,k,m; ll ans[MM]; ll dp_forward[MM],dp_back[MM]; vector<pi> adj[MM],radj[MM];
vector<int> comp[MM];
void dfs(int u){
	for(auto [v,w] : adj[u]){
		dp_forward[v] = min(dp_forward[v],dp_forward[u]+w);
		dfs(v);
	}
}

void dfs1(int u){
	for(auto[v,w]:radj[u]){
		dp_back[v] = min(dp_back[v],dp_back[u]+w);
		dfs1(v);
	}
}

void rec(int l, int r,vector<array<int,5>>& qu){
	//cout << "HERE " << l << " " << r << "\n";
	if(qu.empty()) return;
	if(l == r){
		for(auto[ak,bk,a,b,i]:qu){
			ans[i] = -1;
		}
		return;
	}
	memset(dp_forward,0x3f,sizeof dp_forward); memset(dp_back,0x3f,sizeof dp_back);
	//for(int i = l; i <= r; i++) dp_forward[i] = dp_back[i] = 1e9;
	int mid = (l+r)/2;
	for(int u : comp[mid]){
		// try each node
		dp_forward[u] = dp_back[u] = 0;
		dfs(u);
		dfs1(u);
		//cout << u << " ";
		for(auto[ak,bk,a,b,i]:qu){
			if(ak <= mid && mid < bk){
				//cout << "qu: " << ak << " " << bk << " " << a << " " << b << " " << u << "\n";
				ans[i] = min(ans[i],dp_back[a] + dp_forward[b]);
				continue;
			}
		}
	}
	//cout << "\n";
	vector<array<int,5>> nxt[2];
	for(auto[ak,bk,a,b,i]:qu){
		if(ak <= mid && mid < bk){			
			continue;
		}
		nxt[ak > mid].push_back({ak,bk,a,b,i});
	}
	rec(l,mid,nxt[0]); rec(mid+1,r,nxt[1]);
}

int main(){
	cin.tie(0)->sync_with_stdio(0);
	cin >> k >> n >> m >> o; memset(ans,0x3f,sizeof ans);
	for(int i = 0; i < m; i++){
		int a,b,t; cin >> a >> b >> t; 
		adj[a].emplace_back(b,t); radj[b].emplace_back(a,t);
	}
	for(int i = 0; i < n; i++) comp[i/k].emplace_back(i);
	vector<array<int,5>> qu;
	for(int i = 0; i < o; i++){
		int a,b; cin >> a >> b;
		if(a/k == b/k || a/k > b/k){
			ans[i] = -1;
			continue;
		}
		qu.push_back({a/k,b/k,a,b,i});
	}
	rec(0,(n-1)/k,qu);
	for(int i = 0; i < o; i++) cout << (ans[i]>=1e9 ? -1 : ans[i]) << "\n";
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 516 ms 12564 KB Output is correct
2 Correct 4 ms 4940 KB Output is correct
3 Correct 4 ms 4940 KB Output is correct
4 Correct 4 ms 5000 KB Output is correct
5 Correct 6 ms 5136 KB Output is correct
6 Correct 7 ms 5132 KB Output is correct
7 Correct 6 ms 5068 KB Output is correct
8 Correct 65 ms 11136 KB Output is correct
9 Correct 46 ms 10752 KB Output is correct
10 Correct 17 ms 7040 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3050 ms 9696 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 4940 KB Output is correct
2 Incorrect 4 ms 4940 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 4940 KB Output is correct
2 Incorrect 4 ms 4940 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 516 ms 12564 KB Output is correct
2 Correct 4 ms 4940 KB Output is correct
3 Correct 4 ms 4940 KB Output is correct
4 Correct 4 ms 5000 KB Output is correct
5 Correct 6 ms 5136 KB Output is correct
6 Correct 7 ms 5132 KB Output is correct
7 Correct 6 ms 5068 KB Output is correct
8 Correct 65 ms 11136 KB Output is correct
9 Correct 46 ms 10752 KB Output is correct
10 Correct 17 ms 7040 KB Output is correct
11 Execution timed out 3050 ms 9696 KB Time limit exceeded
12 Halted 0 ms 0 KB -