oj.uz

Submission #500577

# Submission time Handle Problem Language Result Execution time Memory
500577 2021-12-31T12:32:38 Z mars4 Toll (BOI17_toll) C++17
100 / 100
 1799 ms 43844 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp> 

using namespace std;
using namespace __gnu_pbds; 

#define ff              first
#define ss              second
#define ll              int64_t
#define ld              long double
#define nl              cout<<"\n"
#define all(v)          v.begin(),v.end()
#define mset(a,v)       memset((a),(v),sizeof(a))
#define forn(i,a,b)     for(int64_t i=int64_t(a);i<int64_t(b);++i)
#define forb(i,a,b)     for(int64_t i=int64_t(a);i>=int64_t(b);--i)
#define fastio()        ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);

#define mod         1'000'000'007
#define mod2        998'244'353 
#define inf         1'000'000'000'000'007
#define pi          3.14159265358979323846

template<class key,class cmp=std::less<key>>
using ordered_set=tree<key,null_type,cmp,rb_tree_tag,tree_order_statistics_node_update>;

template<class L,class R> ostream& operator<<(ostream& out,pair<L,R> &p)        {return out<<"("<<p.ff<<", "<<p.ss<<")";}
template<class T> ostream& operator<<(ostream& out,vector<T> &v)                {out<<"[";for(auto it=v.begin();it!=v.end();++it){if(it!=v.begin())out<<", ";out<<*it;}return out<<"]";}
template<class T> ostream& operator<<(ostream& out,deque<T> &v)                 {out<<"[";for(auto it=v.begin();it!=v.end();++it){if(it!=v.begin())out<<", ";out<<*it;}return out<<"]";}
template<class T> ostream& operator<<(ostream& out,set<T> &s)                   {out<<"{";for(auto it=s.begin();it!=s.end();++it){if(it!=s.begin())out<<", ";out<<*it;}return out<<"}";}
template<class L,class R> ostream& operator<<(ostream& out,map<L,R> &m)         {out<<"{";for(auto it=m.begin();it!=m.end();++it){if(it!=m.begin())out<<", ";out<<*it;}return out<<"}";}

void dbg_out() {cerr<<"]\n";}
template<typename Head,typename... Tail> 
void dbg_out(Head H,Tail... T) {cerr<<H;if(sizeof...(Tail))cerr<<", ";dbg_out(T...);}
#ifdef LOCAL
	#define dbg(...) cerr<<"["<<#__VA_ARGS__<<"] = [",dbg_out(__VA_ARGS__)
#else
	#define dbg(...)
#endif

//---------------------------------mars4---------------------------------

vector<tuple<ll,ll,ll>> edges;
vector<pair<ll,ll>> queries;
vector<ll> ans;
ll K;

void calc(ll l,ll r,vector<ll> ei,vector<ll> qi)
{
	if(l>=r)
	{
		return;
	}
	ll mid=(l+r)/2;
	vector<ll> elft,erht,emid;
	vector<ll> qlft,qrht,qmid;
	vector<map<ll,ll>> mm(K);
	for(ll i:ei)
	{
		auto [a,b,w]=edges[i];
		if(b/K<=mid)
		{
			elft.push_back(i);
		}
		else if(a/K>mid)
		{
			erht.push_back(i);
		}
		else
		{
			emid.push_back(i);
			mm[a%K][b%K]=w;
		}
	}
	for(ll i:qi)
	{
		auto [a,b]=queries[i];
		if(b/K<=mid)
		{
			qlft.push_back(i);
		}
		else if(a/K>mid)
		{
			qrht.push_back(i);
		}
		else
		{
			qmid.push_back(i);
		}
	}
	vector<map<ll,ll>> mp(K);
	forn(i,(mid+1)*K,(mid+2)*K)
	{
		mp[i%K][i]=0;
	}
	for(ll i:erht)
	{
		auto [a,b,w]=edges[i];
		forn(j,0,K)
		{
			if(mp[j].count(a))
			{
				if(!mp[j].count(b))
				{
					mp[j][b]=mp[j][a]+w;
				}
				else
				{
					mp[j][b]=min(mp[j][b],mp[j][a]+w);
				}
			}
		}
	}
	vector<ll> rev=elft;
	reverse(all(rev));
	forn(i,mid*K,(mid+1)*K)
	{
		mp[i%K][i]=0;
	}
	for(ll i:rev)
	{
		auto [a,b,w]=edges[i];
		forn(j,0,K)
		{
			if(mp[j].count(b))
			{
				if(!mp[j].count(a))
				{
					mp[j][a]=mp[j][b]+w;
				}
				else
				{
					mp[j][a]=min(mp[j][a],mp[j][b]+w);
				}
			}
		}
	}
	for(ll i:qmid)
	{
		auto [a,b]=queries[i];
		if(a/K!=mid and b/K!=mid+1)
		{
			forn(j,0,K)
			{
				forn(k,0,K)
				{
					if(mp[j].count(a) and mm[j].count(k) and mp[k].count(b))
					{
						ans[i]=min(ans[i],mp[j][a]+mm[j][k]+mp[k][b]);
					}
				}
			}
		}
		if(a/K==mid and b/K!=mid+1)
		{
			forn(k,0,K)
			{
				if(mm[a%K].count(k) and mp[k].count(b))
				{
					ans[i]=min(ans[i],mm[a%K][k]+mp[k][b]);
				}
			}
		}
		if(a/K!=mid and b/K==mid+1)
		{
			forn(j,0,K)
			{
				if(mp[j].count(a) and mm[j].count(b%K))
				{
					ans[i]=min(ans[i],mp[j][a]+mm[j][b%K]);
				}
			}
		}
		if(a/K==mid and b/K==mid+1)
		{
			if(mm[a%K].count(b%K))
			{
				ans[i]=min(ans[i],mm[a%K][b%K]);
			}
		}
	}
	calc(l,mid,elft,qlft);
	calc(mid+1,r,erht,qrht);
}

int main()
{
	fastio();
	ll z,n,m,t,k,i,j,l,d,h,r;
	ll q;
	cin>>K>>n>>m>>q;
	edges=vector<tuple<ll,ll,ll>>(m);
	queries=vector<pair<ll,ll>>(q);
	ans=vector<ll>(q,inf);
	for(auto &[l,r,w]:edges)
	{
		cin>>l>>r>>w;
	}
	for(auto &[l,r]:queries)
	{
		cin>>l>>r;
	}
	sort(all(edges));
	vector<ll> ei(m);
	vector<ll> qi(q);
	iota(all(ei),0ll);
	iota(all(qi),0ll);
	calc(0,(n+K-1)/K,ei,qi);
	for(ll i:ans)
	{
		if(i==inf)
		{
			cout<<"-1\n";
		}
		else
		{
			cout<<i<<"\n";
		}
	}
	cerr<<"\nTime elapsed: "<<1000*clock()/CLOCKS_PER_SEC<<"ms\n";
	return 0;
}

Compilation message

toll.cpp: In function 'int main()':
toll.cpp:190:5: warning: unused variable 'z' [-Wunused-variable]
  190 |  ll z,n,m,t,k,i,j,l,d,h,r;
      |     ^
toll.cpp:190:11: warning: unused variable 't' [-Wunused-variable]
  190 |  ll z,n,m,t,k,i,j,l,d,h,r;
      |           ^
toll.cpp:190:13: warning: unused variable 'k' [-Wunused-variable]
  190 |  ll z,n,m,t,k,i,j,l,d,h,r;
      |             ^
toll.cpp:190:15: warning: unused variable 'i' [-Wunused-variable]
  190 |  ll z,n,m,t,k,i,j,l,d,h,r;
      |               ^
toll.cpp:190:17: warning: unused variable 'j' [-Wunused-variable]
  190 |  ll z,n,m,t,k,i,j,l,d,h,r;
      |                 ^
toll.cpp:190:19: warning: unused variable 'l' [-Wunused-variable]
  190 |  ll z,n,m,t,k,i,j,l,d,h,r;
      |                   ^
toll.cpp:190:21: warning: unused variable 'd' [-Wunused-variable]
  190 |  ll z,n,m,t,k,i,j,l,d,h,r;
      |                     ^
toll.cpp:190:23: warning: unused variable 'h' [-Wunused-variable]
  190 |  ll z,n,m,t,k,i,j,l,d,h,r;
      |                       ^
toll.cpp:190:25: warning: unused variable 'r' [-Wunused-variable]
  190 |  ll z,n,m,t,k,i,j,l,d,h,r;
      |                         ^

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 176 ms 11660 KB Output is correct
2 Correct 0 ms 308 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 2 ms 460 KB Output is correct
6 Correct 2 ms 452 KB Output is correct
7 Correct 2 ms 452 KB Output is correct
8 Correct 97 ms 6272 KB Output is correct
9 Correct 66 ms 5292 KB Output is correct
10 Correct 11 ms 972 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 463 ms 18560 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 240 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 312 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 5 ms 1228 KB Output is correct
8 Correct 12 ms 1476 KB Output is correct
9 Correct 142 ms 6360 KB Output is correct
10 Correct 962 ms 32364 KB Output is correct
11 Correct 559 ms 22316 KB Output is correct
12 Correct 166 ms 8316 KB Output is correct
13 Correct 1340 ms 33192 KB Output is correct
14 Correct 599 ms 19792 KB Output is correct
15 Correct 696 ms 25552 KB Output is correct
16 Correct 674 ms 24308 KB Output is correct

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 0 ms 204 KB Output is correct
6 Correct 3 ms 352 KB Output is correct
7 Correct 6 ms 716 KB Output is correct
8 Correct 16 ms 1384 KB Output is correct
9 Correct 11 ms 1024 KB Output is correct
10 Correct 97 ms 5844 KB Output is correct
11 Correct 508 ms 21352 KB Output is correct
12 Correct 882 ms 31816 KB Output is correct
13 Correct 1096 ms 32984 KB Output is correct
14 Correct 749 ms 28588 KB Output is correct
15 Correct 639 ms 24472 KB Output is correct
16 Correct 645 ms 25184 KB Output is correct

Subtask #4
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 0 ms 204 KB Output is correct
6 Correct 3 ms 352 KB Output is correct
7 Correct 6 ms 716 KB Output is correct
8 Correct 16 ms 1384 KB Output is correct
9 Correct 11 ms 1024 KB Output is correct
10 Correct 97 ms 5844 KB Output is correct
11 Correct 508 ms 21352 KB Output is correct
12 Correct 882 ms 31816 KB Output is correct
13 Correct 1096 ms 32984 KB Output is correct
14 Correct 749 ms 28588 KB Output is correct
15 Correct 639 ms 24472 KB Output is correct
16 Correct 645 ms 25184 KB Output is correct
17 Correct 496 ms 19896 KB Output is correct
18 Correct 0 ms 204 KB Output is correct
19 Correct 0 ms 204 KB Output is correct
20 Correct 0 ms 320 KB Output is correct
21 Correct 0 ms 204 KB Output is correct
22 Correct 1 ms 204 KB Output is correct
23 Correct 2 ms 588 KB Output is correct
24 Correct 7 ms 860 KB Output is correct
25 Correct 23 ms 1392 KB Output is correct
26 Correct 17 ms 1296 KB Output is correct
27 Correct 95 ms 5832 KB Output is correct
28 Correct 870 ms 32156 KB Output is correct
29 Correct 1025 ms 33196 KB Output is correct
30 Correct 669 ms 24292 KB Output is correct

Subtask #5
44.0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 176 ms 11660 KB Output is correct
2 Correct 0 ms 308 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 2 ms 460 KB Output is correct
6 Correct 2 ms 452 KB Output is correct
7 Correct 2 ms 452 KB Output is correct
8 Correct 97 ms 6272 KB Output is correct
9 Correct 66 ms 5292 KB Output is correct
10 Correct 11 ms 972 KB Output is correct
11 Correct 463 ms 18560 KB Output is correct
12 Correct 1 ms 204 KB Output is correct
13 Correct 1 ms 240 KB Output is correct
14 Correct 1 ms 204 KB Output is correct
15 Correct 1 ms 312 KB Output is correct
16 Correct 1 ms 204 KB Output is correct
17 Correct 5 ms 1228 KB Output is correct
18 Correct 12 ms 1476 KB Output is correct
19 Correct 142 ms 6360 KB Output is correct
20 Correct 962 ms 32364 KB Output is correct
21 Correct 559 ms 22316 KB Output is correct
22 Correct 166 ms 8316 KB Output is correct
23 Correct 1340 ms 33192 KB Output is correct
24 Correct 599 ms 19792 KB Output is correct
25 Correct 696 ms 25552 KB Output is correct
26 Correct 674 ms 24308 KB Output is correct
27 Correct 1 ms 204 KB Output is correct
28 Correct 1 ms 204 KB Output is correct
29 Correct 0 ms 204 KB Output is correct
30 Correct 1 ms 204 KB Output is correct
31 Correct 0 ms 204 KB Output is correct
32 Correct 3 ms 352 KB Output is correct
33 Correct 6 ms 716 KB Output is correct
34 Correct 16 ms 1384 KB Output is correct
35 Correct 11 ms 1024 KB Output is correct
36 Correct 97 ms 5844 KB Output is correct
37 Correct 508 ms 21352 KB Output is correct
38 Correct 882 ms 31816 KB Output is correct
39 Correct 1096 ms 32984 KB Output is correct
40 Correct 749 ms 28588 KB Output is correct
41 Correct 639 ms 24472 KB Output is correct
42 Correct 645 ms 25184 KB Output is correct
43 Correct 496 ms 19896 KB Output is correct
44 Correct 0 ms 204 KB Output is correct
45 Correct 0 ms 204 KB Output is correct
46 Correct 0 ms 320 KB Output is correct
47 Correct 0 ms 204 KB Output is correct
48 Correct 1 ms 204 KB Output is correct
49 Correct 2 ms 588 KB Output is correct
50 Correct 7 ms 860 KB Output is correct
51 Correct 23 ms 1392 KB Output is correct
52 Correct 17 ms 1296 KB Output is correct
53 Correct 95 ms 5832 KB Output is correct
54 Correct 870 ms 32156 KB Output is correct
55 Correct 1025 ms 33196 KB Output is correct
56 Correct 669 ms 24292 KB Output is correct
57 Correct 1799 ms 43844 KB Output is correct
58 Correct 98 ms 6312 KB Output is correct
59 Correct 548 ms 22456 KB Output is correct