Submission #235306

#	Time	Username	Problem	Language	Result	Execution time	Memory
235306		eohomegrownapps	Toll (BOI17_toll)	C++14	100 / 100	602 ms	16632 KiB

toll

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

vector<vector<pair<int,int>>> adjlist;
int k,n,num;
int INF = 1e9;

pair<int,int> toCoord(int x){
	return {x/k,x%k};
}

vector<vector<int>> combine(vector<vector<int>> a, vector<vector<int>> b, int m){
	//cout<<m<<endl;
	//x - index of rightmost connector
	vector<vector<int>> ans(k,vector<int>(k,INF));
	for (int i = 0; i<k; i++){
		for (int j = 0; j<k; j++){
			//get from a[i][_] to b[_][j]
			int mindist = INF;
			for (int x = 0; x<k; x++){
				if (a[i][x]==INF){continue;}
				for (auto v : adjlist[m*k+x]){
					//cout<<v.first<<" "<<v.second<<endl;
					int node = (v.first)%k;
					int dist = v.second;
					//cout<<node<<endl;
					if (b[node][j]==INF){continue;}
					mindist=min(mindist,a[i][x]+b[node][j]+dist);
				}
			}
			ans[i][j]=mindist;
		}
	}
	return ans;
}

struct Node{
	int s,e,m;
	vector<vector<int>> v;
	Node *l, *r;

	Node(int _s, int _e){
		s=_s;e=_e;
		if (s==e){
			v.resize(k,vector<int>(k,INF));
			for (int i = 0; i<k; i++){
				v[i][i]=0;
			}
			return;
		}
		m = (s+e)/2;
		l = new Node(s,m);
		r = new Node(m+1,e);
		v = combine(l->v,r->v,m);
	}

	vector<vector<int>> query(int a, int b){
		if (a==s&&b==e){
			return v;
		}
		if (b<=m){
			return l->query(a,b);
		} else if (m<a){
			return r->query(a,b);
		} else {
			return combine(l->query(a,m),r->query(m+1,b),m);
		}
	}
};

int main(){
	//cin.tie(0);
	//ios_base::sync_with_stdio(0);
	int m,o;
	cin>>k>>n>>m>>o;
	adjlist.resize(n);
	for (int i = 0; i<m; i++){
		int a,b,t;
		cin>>a>>b>>t;
		adjlist[a].push_back({b,t});
	}
	num=(n+k-1)/k;
	Node *root = new Node(0,num-1);
	for (int i = 0; i<o; i++){
		int a,b;
		cin>>a>>b;
		if (a==b){
			cout<<0<<'\n';
			continue;
		}
		auto ai = toCoord(a);
		auto bi = toCoord(b);
		if (ai.first>=bi.first){
			cout<<-1<<'\n';
			continue;
		}
		auto q = root->query(ai.first,bi.first);
		int ans = q[ai.second][bi.second];
		if (ans==INF){
			cout<<-1<<'\n';
		} else {
			cout<<ans<<'\n';
		}
	}
}

• Subtask 1: 7 / 7
• Subtask 2: 10 / 10
• Subtask 3: 8 / 8
• Subtask 4: 31 / 31
• Subtask 5: 44 / 44