oj.uz

Submission #233490

# Submission time Handle Problem Language Result Execution time Memory
233490 2020-05-20T17:44:57 Z eohomegrownapps Toll (BOI17_toll) C++14
7 / 100
 1995 ms 9976 KB 
#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][50001][6];
	for (int i = 0; i<2; i++){
		for (int j = 0; j<n; j++){
			for (int x = 0; x<k; x++){
				distfrom[i][j][k]=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][x%k]=0;
			from.insert(x);
		}
		for (int j = 0; j<k; j++){
			if (i*k+j>=n){break;}
			for (int nf : from){
				distfrom[curr][nf][j]=INF;
				for (auto p : adjlist[i*k+j]){
					distfrom[curr][nf][j]=min(distfrom[curr][nf][j],distfrom[!curr][nf][p.first%k]+p.second);
				}
			}
			for (auto p : to[i*k+j]){
				if (distfrom[curr][p.first][j]!=INF){
					ans[p.second]=distfrom[curr][p.first][j];
				}
				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.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1991 ms 8952 KB Output is correct
2 Correct 4 ms 384 KB Output is correct
3 Correct 4 ms 384 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 7 ms 640 KB Output is correct
6 Correct 7 ms 640 KB Output is correct
7 Correct 7 ms 512 KB Output is correct
8 Correct 1962 ms 9976 KB Output is correct
9 Correct 1995 ms 9848 KB Output is correct
10 Correct 1571 ms 7544 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 49 ms 7800 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

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

Subtask #4
0 / 31.0

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

Subtask #5
0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 1991 ms 8952 KB Output is correct
2 Correct 4 ms 384 KB Output is correct
3 Correct 4 ms 384 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 7 ms 640 KB Output is correct
6 Correct 7 ms 640 KB Output is correct
7 Correct 7 ms 512 KB Output is correct
8 Correct 1962 ms 9976 KB Output is correct
9 Correct 1995 ms 9848 KB Output is correct
10 Correct 1571 ms 7544 KB Output is correct
11 Incorrect 49 ms 7800 KB Output isn't correct
12 Halted 0 ms 0 KB -