oj.uz

Submission #235304

# Submission time Handle Problem Language Result Execution time Memory
235304 2020-05-27T16:04:05 Z eohomegrownapps Toll (BOI17_toll) C++14
0 / 100
 125 ms 16632 KB 
#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]){
					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});
		adjlist[b].push_back({a,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
0 / 7.0

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

Subtask #2
0 / 10.0

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

Subtask #3
0 / 8.0

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

Subtask #4
0 / 31.0

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

Subtask #5
0 / 44.0

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