Submission #233492

#	Time	Username	Problem	Language	Result	Execution time	Memory
233492		eohomegrownapps	Toll (BOI17_toll)	C++14	56 / 100	3030 ms	8348 KiB

toll

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

vector<vector<pair<int,int>>> adjlist;

int INF = 1e9;

int main(){
	cin.tie(0);
	ios_base::sync_with_stdio(0);
	int k,n,m,o;
	cin>>k>>n>>m>>o;
	adjlist.resize((n/k)*k+k);
	for (int i = 0; i<m; i++){
		int a,b,t;
		cin>>a>>b>>t;
		adjlist[b].push_back({a,t});
	}
	unordered_set<int> from;
	vector<vector<int>> addat(n/k+1);
	//vector<vector<vector<int>>> distfrom(2,vector<vector<int>>(n,vector<int>(k,INF)));
	int distfrom[2][6][50000];
	for (int i = 0; i<2; i++){
		for (int x = 0; x<k; x++){
			for (int j = 0; j<n; j++){
				distfrom[i][x][j]=INF;
			}
		}
	}
	vector<vector<pair<int,int>>> to(n);
	vector<int> fromcnt(n,0);
	vector<int> ans(o,-1);
	for (int i = 0; i<o; i++){
		int a,b;
		cin>>a>>b;
		//from.push_back(a);
		addat[a/k].push_back(a);
		to[b].push_back({a,i});
		fromcnt[a]++;
	}
	//sort(from.begin(),from.end());
	//from.erase(unique(from.begin(),from.end()),from.end());
	bool curr = 0;
	for (int i = 1; i<=(n/k+1); i++){
		//cout<<i<<endl;
		for (int x : addat[i-1]){
			distfrom[!curr][x%k][x]=0;
			from.insert(x);
		}
		for (int j = 0; j<k; j++){
			if (i*k+j>=n){break;}
			for (int nf : from){
				distfrom[curr][j][nf]=INF;
				for (auto p : adjlist[i*k+j]){
					distfrom[curr][j][nf]=min(distfrom[curr][j][nf],distfrom[!curr][p.first%k][nf]+p.second);
				}
			}
			for (auto p : to[i*k+j]){
				if (distfrom[curr][j][p.first]!=INF){
					ans[p.second]=distfrom[curr][j][p.first];
				}
				fromcnt[p.first]--;
				if (fromcnt[p.first]==0){
					from.erase(p.first);
				}
			}
		}
		curr=!curr;
	}
	for (int i = 0; i<o; i++){
		cout<<ans[i]<<'\n';
	}
}

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