Submission #751662

#	Time	Username	Problem	Language	Result	Execution time	Memory
751662		Warinchai	Voting Cities (NOI22_votingcity)	C++14	100 / 100	140 ms	10332 KiB

Main

#include<bits/stdc++.h>
using namespace std;
vector<pair<int,long long> >g[5005];
long long dis[5005][2][2][2][2][2];
struct info{
	int one,two,three,four,five;
	bool operator<(const info &x)const
	{
		if(one==x.one){
			if(two==x.two){
				if(three==x.three){
					if(four==x.four){
						return five<x.five;
					}else{
						return four<x.four;
					}
				}else{
					return three<x.three;
				}
			}else{
				return two<x.two;
			}
		}else{
			return one<x.one;
		}
	}
};
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	int n,e,k;
	cin>>n>>e>>k;
	vector<int>v;
	for(int i=0;i<k;i++){
		int a;
		cin>>a;
		v.push_back(a);
	}
	for(int i=0;i<e;i++){
		long long u,v,c;
		cin>>u>>v>>c;
		g[v].push_back({u,c});
	}
	for(int i=0;i<n;i++){
		for(int i1=0;i1<=1;i1++){
			for(int i2=0;i2<=1;i2++){
				for(int i3=0;i3<=1;i3++){
					for(int i4=0;i4<=1;i4++){
						for(int i5=0;i5<=1;i5++){
							dis[i][i1][i2][i3][i4][i5]=LLONG_MAX;
						}
					}
				}
			}
		}
	}
	info nd;
	nd.one=0;
	nd.two=0;
	nd.three=0;
	nd.four=0;
	nd.five=0;
	priority_queue<pair<long long,pair<int,info> >,vector<pair<long long,pair<int,info> > >,greater<pair<long long,pair<int,info> > > >pq;
	for(int i=0;i<k;i++){
		pq.push({0,{v[i],nd}});
		dis[v[i]][0][0][0][0][0]=0;
	}
	while(!pq.empty()){
		long long d=pq.top().first;
		int l=pq.top().second.first;
		info x= pq.top().second.second;
		pq.pop();
		for(int i=0;i<g[l].size();i++){
			if(x.one==0){
				if(d+g[l][i].second*9/10<dis[g[l][i].first][1][x.two][x.three][x.four][x.five]){
					dis[g[l][i].first][1][x.two][x.three][x.four][x.five]=d+g[l][i].second*9/10;
					x.one=1;
					pq.push({dis[g[l][i].first][1][x.two][x.three][x.four][x.five],{g[l][i].first,x}});
					x.one=0;
				}
			}else{
				if(d+g[l][i].second<dis[g[l][i].first][1][x.two][x.three][x.four][x.five]){
					dis[g[l][i].first][1][x.two][x.three][x.four][x.five]=d+g[l][i].second;
					pq.push({dis[g[l][i].first][1][x.two][x.three][x.four][x.five],{g[l][i].first,x}});
				}
			}
			if(x.two==0){
				if(d+g[l][i].second*8/10<dis[g[l][i].first][x.one][1][x.three][x.four][x.five]){
					dis[g[l][i].first][x.one][1][x.three][x.four][x.five]=d+g[l][i].second*8/10;
					x.two=1;
					pq.push({dis[g[l][i].first][x.one][1][x.three][x.four][x.five],{g[l][i].first,x}});
					x.two=0;
				}
			}else{
				if(d+g[l][i].second<dis[g[l][i].first][x.one][1][x.three][x.four][x.five]){
					dis[g[l][i].first][x.one][1][x.three][x.four][x.five]=d+g[l][i].second;
					pq.push({dis[g[l][i].first][x.one][1][x.three][x.four][x.five],{g[l][i].first,x}});
				}
			}
			if(x.three==0){
				if(d+g[l][i].second*7/10<dis[g[l][i].first][x.one][x.two][1][x.four][x.five]){
					dis[g[l][i].first][x.one][x.two][1][x.four][x.five]=d+g[l][i].second*7/10;
					x.three=1;
					pq.push({dis[g[l][i].first][x.one][x.two][1][x.four][x.five],{g[l][i].first,x}});
					x.three=0;
				}
			}else{
				if(d+g[l][i].second<dis[g[l][i].first][x.one][x.two][1][x.four][x.five]){
					dis[g[l][i].first][x.one][x.two][1][x.four][x.five]=d+g[l][i].second;
					pq.push({dis[g[l][i].first][x.one][x.two][1][x.four][x.five],{g[l][i].first,x}});
				}
			}
			if(x.four==0){
				if(d+g[l][i].second*6/10<dis[g[l][i].first][x.one][x.two][x.three][1][x.five]){
					dis[g[l][i].first][x.one][x.two][x.three][1][x.five]=d+g[l][i].second*6/10;
					x.four=1;
					pq.push({dis[g[l][i].first][x.one][x.two][x.three][1][x.five],{g[l][i].first,x}});
					x.four=0;
				}
			}else{
				if(d+g[l][i].second<dis[g[l][i].first][x.one][x.two][x.three][1][x.five]){
					dis[g[l][i].first][x.one][x.two][x.three][1][x.five]=d+g[l][i].second;
					pq.push({dis[g[l][i].first][x.one][x.two][x.three][1][x.five],{g[l][i].first,x}});
				}
			}
			if(x.five==0){
				if(d+g[l][i].second*5/10<dis[g[l][i].first][x.one][x.two][x.three][x.four][1]){
					dis[g[l][i].first][x.one][x.two][x.three][x.four][1]=d+g[l][i].second*5/10;
					x.five=1;
					pq.push({dis[g[l][i].first][x.one][x.two][x.three][x.four][1],{g[l][i].first,x}});
					x.five=0;
				}
			}else{
				if(d+g[l][i].second<dis[g[l][i].first][x.one][x.two][x.three][x.four][1]){
					dis[g[l][i].first][x.one][x.two][x.three][x.four][1]=d+g[l][i].second;
					pq.push({dis[g[l][i].first][x.one][x.two][x.three][x.four][1],{g[l][i].first,x}});
				}
			}
			if(d+g[l][i].second<dis[g[l][i].first][x.one][x.two][x.three][x.four][x.five]){
				dis[g[l][i].first][x.one][x.two][x.three][x.four][x.five]=d+g[l][i].second;
				pq.push({dis[g[l][i].first][x.one][x.two][x.three][x.four][x.five],{g[l][i].first,x}});
			}
		}
	}
	int q;
	cin>>q;
	for(int i=0;i<q;i++){
		int s,p1,p2,p3,p4,p5;
		long long ans=0;
		cin>>s>>p1>>p2>>p3>>p4>>p5;
		long long mn=LLONG_MAX;
		for(int i1=0;i1<=1;i1++){
			if(i1==1&&p1==-1){
				continue;
			}
			for(int i2=0;i2<=1;i2++){
				if(i2==1&&p2==-1){
					continue;
				}
				for(int i3=0;i3<=1;i3++){
					if(i3==1&&p3==-1){
						continue;
					}
					for(int i4=0;i4<=1;i4++){
						if(i4==1&&p4==-1){
							continue;
						}
						for(int i5=0;i5<=1;i5++){
							if(i5==1&&p5==-1){
								continue;
							}
							if(dis[s][i1][i2][i3][i4][i5]==LLONG_MAX){
								continue;
							}
						//	cout<<i1<<" "<<i2<<" "<<i3<<" "<<i4<<" "<<i5<<" "<<dis[s][i1][i2][i3][i4][i5]<<" "<<dis[s][i1][i2][i3][i4][i5]+i1*p1+i2*p2+i3*p3+i4*p4+i5*p5<<"\n";
							if(dis[s][i1][i2][i3][i4][i5]+i1*p1+i2*p2+i3*p3+i4*p4+i5*p5<mn){
								mn=dis[s][i1][i2][i3][i4][i5]+i1*p1+i2*p2+i3*p3+i4*p4+i5*p5;
							}
						}
					}
				}
			}
		}
		if(mn==LLONG_MAX||mn<0){
			cout<<"-1\n";
		}else{
			cout<<mn<<"\n";
		}
	}
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:73:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   73 |   for(int i=0;i<g[l].size();i++){
      |               ~^~~~~~~~~~~~
Main.cpp:149:13: warning: unused variable 'ans' [-Wunused-variable]
  149 |   long long ans=0;
      |             ^~~

• Subtask 1: 5 / 5
• Subtask 2: 5 / 5
• Subtask 3: 5 / 5
• Subtask 4: 5 / 5
• Subtask 5: 5 / 5
• Subtask 6: 10 / 10
• Subtask 7: 15 / 15
• Subtask 8: 50 / 50