Submission #258128

#	Time	Username	Problem	Language	Result	Execution time	Memory
258128		Nicholas_Patrick	Cities (BOI16_cities)	C++17	74 / 100	4056 ms	59568 KiB

cities

#pragma GCC optimize("O3")
#include <cstdio>
#include <queue>
#include <random>
#include <algorithm>
using namespace std;

int main(){
	int n, k, m;
	scanf("%d%d%d", &n, &k, &m);
	vector <vector <int> > adjLis1(n);
	vector <vector <long long> > disLis1(n);
	vector <int> important(k);
	for(int& i:important){
		scanf("%d", &i);
		i--;
	}
	while(k<4){
		important.push_back(important.back());
		k++;
	}
	for(int i = m;i --;){
		int a, b, c;
		scanf("%d%d%d", &a, &b, &c);
		a--;b--;
		adjLis1[a].push_back(b);
		disLis1[a].push_back(c);
		adjLis1[b].push_back(a);
		disLis1[b].push_back(c);
	}
	vector <vector <long long> > multisource(k, vector <long long> (n, 1e14));
	for(int i = 0;i < k;i ++){
		vector <long long>& dist=multisource[i];
		int source=important[i];
		priority_queue <pair <long long, int>, vector <pair <long long, int> >, greater <pair <long long, int> > > dijkstra;
		dist[source]=0ll;
		dijkstra.push(make_pair(dist[source], source));
		while(!dijkstra.empty()){
			int x=dijkstra.top().second;
			long long d=dijkstra.top().first;
			dijkstra.pop();
			if(dist[x]!=d)
				continue;
			for(int i = 0;i < adjLis1[x].size();i ++){
				int y=adjLis1[x][i];
				long long dd=disLis1[x][i];
				if(dist[y]>d+dd){
					dist[y]=d+dd;
					dijkstra.push(make_pair(dist[y], y));
				}
			}
		}
	}
	if(k==5){
		mt19937 rng(38752);
		shuffle(important.begin(), important.end(), rng);
		long long best=1e14;
		vector <long long> dist;
		for(int i = 0;i < 15;i ++){
			//test here
			//construct graph
			/*
				0..n-1		:layer 1
				n..2n-1		:layer 2
				2n			:source
				2n+1		:sink

				max flow but not maxflow :v
			*/
			vector <vector <int> > adjLis2(n*2+2);
			vector <vector <long long> > disLis2(n*2+2);
			for(int i = 0;i < n;i ++){
				for(int j = 0;j < adjLis1[i].size();j ++){
					//layer1
					adjLis2[i].push_back(adjLis1[i][j]);
					disLis2[i].push_back(disLis1[i][j]);
					//layer2
					adjLis2[i+n].push_back(adjLis1[i][j]+n);
					disLis2[i+n].push_back(disLis1[i][j]);
					if(clock()>3.99*CLOCKS_PER_SEC){
						printf("%lld\n", best);
						return 0;
					}
				}
				//sink --> layer1
				adjLis2[2*n].push_back(i);
				disLis2[2*n].push_back(multisource[1][i]+multisource[2][i]);
				//layer1 --> layer2
				adjLis2[i].push_back(i+n);
				disLis2[i].push_back(multisource[0][i]);
				//layer2 --> sink
				adjLis2[i+n].push_back(2*n+1);
				disLis2[i+n].push_back(multisource[3][i]+multisource[4][i]);
					if(clock()>3.99*CLOCKS_PER_SEC){
						printf("%lld\n", best);
						return 0;
					}
			}
			//dijkstra again
			dist.assign(n*2+2, 1e14);
			int source=n*2, sink=n*2+1;
			priority_queue <pair <long long, int>, vector <pair <long long, int> >, greater <pair <long long, int> > > dijkstra;
			dist[source]=0ll;
			dijkstra.push(make_pair(dist[source], source));
			while(!dijkstra.empty()){
				int x=dijkstra.top().second;
				long long d=dijkstra.top().first;
				dijkstra.pop();
				if(dist[x]!=d)
					continue;
				if(x==sink)
					break;
				for(int i = 0;i < adjLis2[x].size();i ++){
					int y=adjLis2[x][i];
					long long dd=disLis2[x][i];
					if(dist[y]>d+dd){
						dist[y]=d+dd;
						dijkstra.push(make_pair(dist[y], y));
					}
					if(clock()>3.99*CLOCKS_PER_SEC){
						printf("%lld\n", best);
						return 0;
					}
				}
			}
			best=min(best, dist[sink]);
			//switching here
			if(i%3==0){
				// swap(important[2], important[3]);
				swap(multisource[2], multisource[3]);
			}else if(i%3==1){
				// swap(important[2], important[4]);
				swap(multisource[2], multisource[4]);
			}else if(i%3==2){
				if(i==2){
					// swap(important[0], important[1]);
					swap(multisource[0], multisource[1]);
				}else if(i==5){
					// swap(important[0], important[4]);
					swap(multisource[0], multisource[4]);
				}else if(i==8){
					// swap(important[0], important[3]);
					swap(multisource[0], multisource[3]);
				}else if(i==11){
					// swap(important[0], important[2]);
					swap(multisource[0], multisource[2]);
				}else{
					// :)
				}
			}
		}
		printf("%lld\n", best);
	}else{
		long long best=1e14;
		vector <long long> dist;
		for(int i = 0;i < 3;i ++){
			//test here
			//construct graph
			/*
				0..n-1		:layer 1
				n			:source
				n+1		:sink

				max flow but not maxflow :v
			*/
			vector <vector <int> > adjLis2(n+2);
			vector <vector <long long> > disLis2(n+2);
			for(int i = 0;i < n;i ++){
				for(int j = 0;j < adjLis1[i].size();j ++){
					//layer1
					adjLis2[i].push_back(adjLis1[i][j]);
					disLis2[i].push_back(disLis1[i][j]);
				}
				//sink --> layer1
				adjLis2[n].push_back(i);
				disLis2[n].push_back(multisource[0][i]+multisource[1][i]);
				//layer1 --> sink
				adjLis2[i].push_back(n+1);
				disLis2[i].push_back(multisource[2][i]+multisource[3][i]);
			}
			//dijkstra again
			dist.assign(n+2, 1e14);
			int source=n, sink=n+1;
			priority_queue <pair <long long, int>, vector <pair <long long, int> >, greater <pair <long long, int> > > dijkstra;
			dist[source]=0ll;
			dijkstra.push(make_pair(dist[source], source));
			while(!dijkstra.empty()){
				int x=dijkstra.top().second;
				long long d=dijkstra.top().first;
				dijkstra.pop();
				if(dist[x]!=d)
					continue;
				if(x==sink)
					break;
				for(int i = 0;i < adjLis2[x].size();i ++){
					int y=adjLis2[x][i];
					long long dd=disLis2[x][i];
					if(dist[y]>d+dd){
						dist[y]=d+dd;
						dijkstra.push(make_pair(dist[y], y));
					}
				}
			}
			best=min(best, dist[sink]);
			//switching here
			if(i%3==0){
				swap(multisource[1], multisource[2]);
			}else if(i%3==1){
				swap(multisource[1], multisource[3]);
			}else if(i%3==2){
				// :)
			}
		}
		printf("%lld\n", best);
	}
}

Compilation message (stderr)

cities.cpp: In function 'int main()':
cities.cpp:44:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int i = 0;i < adjLis1[x].size();i ++){
                  ~~^~~~~~~~~~~~~~~~~~~
cities.cpp:73:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int j = 0;j < adjLis1[i].size();j ++){
                   ~~^~~~~~~~~~~~~~~~~~~
cities.cpp:113:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0;i < adjLis2[x].size();i ++){
                   ~~^~~~~~~~~~~~~~~~~~~
cities.cpp:169:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int j = 0;j < adjLis1[i].size();j ++){
                   ~~^~~~~~~~~~~~~~~~~~~
cities.cpp:195:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0;i < adjLis2[x].size();i ++){
                   ~~^~~~~~~~~~~~~~~~~~~
cities.cpp:10:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d%d", &n, &k, &m);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~
cities.cpp:15:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &i);
   ~~~~~^~~~~~~~~~
cities.cpp:24: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);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 22 / 22
• Subtask 2: 14 / 14
• Subtask 3: 15 / 15
• Subtask 4: 23 / 23
• Subtask 5: 0 / 26