Submission #135704

#	Time	Username	Problem	Language	Result	Execution time	Memory
135704		khsoo01	Toll (BOI17_toll)	C++11	100 / 100	119 ms	17836 KiB

toll

#include<bits/stdc++.h>
using namespace std;
const int inf = 1e9;
int s, n, m, o;

struct way {
	int t[5][5];
	way() {
		for(int i=0;i<5;i++) {
			for(int j=0;j<5;j++) {
				t[i][j] = inf;
			}
		}
	}
	way operator + (way T) {
		way ret;
		for(int i=0;i<s;i++) {
			for(int j=0;j<s;j++) {
				for(int k=0;k<s;k++) {
					ret.t[i][j] = min(ret.t[i][j], t[i][k]+T.t[k][j]);
				}
			}
		}
		return ret;
	}
};

struct segtree {
	way val[144444];
	int lim;
	void init () {
		for(lim = 1; lim <= n/s; lim <<= 1);
	}
	void update (int S, int E, int V) {
		val[lim+S/s].t[S%s][E%s] = V;
	}
	void buildup () {
		for(int i = lim; --i; ) {
			val[i] = val[2*i] + val[2*i+1];
		}
	}
	int query (int S, int E) {
		if(S == E) return 0;
		if(S/s >= E/s) return inf;
		way ra, rb, ret;
		for(int i=0;i<s;i++) {
			ra.t[i][i] = rb.t[i][i] = 0;
		}
		int SS = lim + S/s, SE = lim + E/s - 1;
		while(SS <= SE) {
			if(SS%2 == 1) {ra = ra + val[SS]; SS++;}
			if(SE%2 == 0) {rb = val[SE] + rb; SE--;}
			SS >>= 1; SE >>= 1;
		}
		ret = ra + rb;
		return ret.t[S%s][E%s];
	}
} seg;

int main()
{
	scanf("%d%d%d%d",&s,&n,&m,&o);
	seg.init();
	for(int i=1;i<=m;i++) {
		int A, B, C;
		scanf("%d%d%d",&A,&B,&C);
		seg.update(A, B, C);
	}
	seg.buildup();
	while(o--) {
		int S, E;
		scanf("%d%d",&S,&E);
		int ret = seg.query(S,E);
		printf("%d\n",ret == inf ? -1 : ret);
	}
}

Compilation message (stderr)

toll.cpp: In function 'int main()':
toll.cpp:62:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d%d%d",&s,&n,&m,&o);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
toll.cpp:66:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d%d",&A,&B,&C);
   ~~~~~^~~~~~~~~~~~~~~~~~~
toll.cpp:72:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d",&S,&E);
   ~~~~~^~~~~~~~~~~~~~

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