Submission #129360

#	Time	Username	Problem	Language	Result	Execution time	Memory
129360		davitmarg	Toll (BOI17_toll)	C++17	100 / 100	297 ms	66908 KiB

toll

/*DavitMarg*/
#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <string>
#include <cstring>
#include <map>
#include <set>
#include <queue>
#include <iomanip>
#include <stack>
#include <cassert>
#include <iterator>
#include <bitset>
#include <fstream>
#define mod 1000000007ll
#define LL long long
#define LD long double
#define MP make_pair
#define PB push_back
#define all(v) v.begin(),v.end()
using namespace std;
 
struct node
{
    LL d[6][6];
    node()
    {
        for(int i=0;i<5;i++)
			for(int j=0;j<5;j++)
                d[i][j]=mod*100005ll;
    }
};
 
LL k,n,m,o;
bool used[50004];
vector<int> a[50004];
vector<pair<int,LL>> g[50004];
node t[4*50004];
 
node merge(node a,node b,int pos)
{
	node r;
    for(int s=0;s<k;s++)
		for(int e=0;e<k;e++)
            for(int v=pos*k;v<pos*k+k;v++)
                for(int i=0;i<g[v].size();i++)
				{
					int to=g[v][i].first;
					LL d=g[v][i].second;
                    r.d[s][e]=min( a.d[s][v-pos*k]+b.d[to-pos*k-k][e]+d ,r.d[s][e]);
				}
	return r;
}
 
void build(int v,int l,int r)
{
    if(l==r)
	{
        for(int i=0;i<k;i++)
            t[v].d[i][i]=0;
        return;
	}
	int m=(l+r)/2;
    build(v*2,l,m);
    build(v*2+1,m+1,r);
    t[v]=merge(t[v*2],t[v*2+1],m);
}
 
node get(int v,int l,int r,int i,int j)
{
    if(i>j)
        return node();
    if(l==i && r==j)
		return t[v];
	int m=(l+r)/2;
	if(j<=m)
        return get(v*2,l,m,i,j);
	else if(i>=m+1)
        return get(v*2+1,m+1,r,i,j);
	else
		return merge(
			get(v*2,l,m,i,m),
			get(v*2+1,m+1,r,m+1,j),
			m
		);
}
 
int main()
{
	cin>>k>>n>>m>>o;
    while(m--)
	{
		int a,b;
		LL d;
		scanf("%d%d%lld",&a,&b,&d);
		g[a].PB(MP(b,d));
	}
 
    for(int i=0;i<n;i++)
        a[i/k].PB(i);
 
    n--;
    build(1,0,n/k);
	while(o--)
	{
		int a,b;
		scanf("%d%d",&a,&b);
		LL ans=get(1,0,n/k,a/k,b/k).d[a-(a/k)*k][b-(b/k)*k];
		if(ans>=mod*100005ll)
			ans=-1;
        printf("%lld\n",ans);
	}
 
	return 0;
}
 
 
/*
 
5 14 5 5
0 5 9
5 12 10
0 7 7
7 12 8
4 7 10
0 12
0 5
0 7
7 12
0 13
 
*/

Compilation message (stderr)

toll.cpp: In function 'node merge(node, node, int)':
toll.cpp:48:30: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                 for(int i=0;i<g[v].size();i++)
                             ~^~~~~~~~~~~~
toll.cpp: In function 'int main()':
toll.cpp:97:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d%lld",&a,&b,&d);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~
toll.cpp:109: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: 7 / 7
• Subtask 2: 10 / 10
• Subtask 3: 8 / 8
• Subtask 4: 31 / 31
• Subtask 5: 44 / 44