oj.uz

Submission #124791

# Submission time Handle Problem Language Result Execution time Memory
124791 2019-07-04T02:02:47 Z model_code Toll (BOI17_toll) C++17
8 / 100
 157 ms 20188 KB 
#include <cassert>
#include<stdio.h>
#include<vector>
#include<iostream>
#define llint long long 

using namespace std;

const llint bigVal = ((long long) 100000)*((long long) 100001);
int K;

// shortest path matrix
struct spm {
	vector<vector<llint> > M;
	
	spm(int dim, llint initVal, llint diagVal) {
		M = vector<vector<llint> > (dim, vector<llint> (dim, initVal));
		for(int i = 0; i < dim; ++i) M[i][i] = diagVal;
	}
	
	inline int dim() {return M.size();}
};

// overload + to (min,+) product for spm's.
spm operator + (spm L, spm R) {
	int dim = L.dim();
	spm ans(dim, 0, 0);
	for(int i = 0; i < dim; ++i) {
		for(int j = 0; j < dim; ++j) {
			llint cur = L.M[i][0] + R.M[0][j];
			for(int k = 1; k < dim; ++k) {
				llint newVal = L.M[i][k] + R.M[k][j];
				cur = cur < newVal ? cur : newVal;
			}
			ans.M[i][j] = cur;
		}
	}
	return ans;
}

// binary segment tree for spms without update capability. 
struct bst {
	vector<spm> a;
	int N;
	int offs;
	
	bst(vector<spm> initArray) {
		int n = initArray.size();
		N = 2;
		while(N < 2*n+4) N *= 2;
		offs = N/2 + 1;
		a = vector<spm> (N, spm(K, bigVal, bigVal));
		for(int i = 0; i < n; ++i) a[i+offs] = initArray[i];
		for(int i = offs-2; i > 0; --i) a[i] = a[2*i] + a[(2*i)+1];
	}
	
	spm sum(int i, int j) {
		int L = i + offs - 1;
		int R = j + offs + 1;
		spm Lans(K,bigVal,(llint)0);
		spm Rans(K,bigVal,(llint)0);
		while(true) {
			bool Lright = L%2 == 0;
			bool Rleft = R%2 == 1;
			L /= 2; 
			R /= 2;
			if(L==R) break;
			if(Lright) Lans = Lans + a[2*L+1];
			if(Rleft) Rans = a[2*R] + Rans;
		}
		return Lans + Rans;
	}
};

int main() {
	
	int N,M,O;
		
	// read input
	scanf("%d%d%d%d",&K,&N,&M,&O);
    assert(O <= 100);
	vector<spm> initArray(N/K, spm(K, bigVal, bigVal));
	for(int i = 0; i < M; ++i) {
		int a,b,t;
		scanf("%d%d%d",&a,&b,&t);
		initArray[a/K].M[a%K][b%K] = t;
	}

	// make bst
	bst T(initArray);
	
	// answer queries
	for(int i = 0; i < O; ++i) {
		int a,b;
		scanf("%d%d",&a,&b);
		if(a/K >= b/K) {
			printf("-1\n");
		} else {
			spm ans = T.sum(a/K, b/K-1);
			printf("%lld\n", (ans.M[a%K][b%K] < bigVal ? ans.M[a%K][b%K] : -1));
		}
	}
	
	return 0;
}

Compilation message

toll.cpp: In function 'int main()':
toll.cpp:80:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d%d%d",&K,&N,&M,&O);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
toll.cpp:85:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d%d",&a,&b,&t);
   ~~~~~^~~~~~~~~~~~~~~~~~~
toll.cpp:95:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d",&a,&b);
   ~~~~~^~~~~~~~~~~~~~

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Runtime error 3 ms 376 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 3 ms 504 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 256 KB Output is correct
3 Correct 2 ms 256 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 256 KB Output is correct
6 Correct 4 ms 632 KB Output is correct
7 Correct 4 ms 632 KB Output is correct
8 Correct 5 ms 632 KB Output is correct
9 Correct 4 ms 632 KB Output is correct
10 Correct 87 ms 20188 KB Output is correct
11 Correct 102 ms 17656 KB Output is correct
12 Correct 131 ms 19676 KB Output is correct
13 Correct 157 ms 19796 KB Output is correct
14 Correct 114 ms 19756 KB Output is correct
15 Correct 67 ms 11248 KB Output is correct
16 Correct 69 ms 11372 KB Output is correct

Subtask #4
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 256 KB Output is correct
3 Correct 2 ms 256 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 256 KB Output is correct
6 Correct 4 ms 632 KB Output is correct
7 Correct 4 ms 632 KB Output is correct
8 Correct 5 ms 632 KB Output is correct
9 Correct 4 ms 632 KB Output is correct
10 Correct 87 ms 20188 KB Output is correct
11 Correct 102 ms 17656 KB Output is correct
12 Correct 131 ms 19676 KB Output is correct
13 Correct 157 ms 19796 KB Output is correct
14 Correct 114 ms 19756 KB Output is correct
15 Correct 67 ms 11248 KB Output is correct
16 Correct 69 ms 11372 KB Output is correct
17 Runtime error 2 ms 504 KB Execution killed with signal 11 (could be triggered by violating memory limits)
18 Halted 0 ms 0 KB -

Subtask #5
0 / 44.0

# Verdict Execution time Memory Grader output
1 Runtime error 3 ms 376 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -