Submission #332476

#	Time	Username	Problem	Language	Result	Execution time	Memory
332476		egas	Swapping Cities (APIO20_swap)	C++14	13 / 100	1227 ms	43124 KiB

swap

#include <bits/stdc++.h>
using namespace std;
map<int,set<int>> adj;
multiset<int> ms;
map<pair<int,int>,int> edwt;
int SUBTASK1=0;
bool isCyc=0;
bool isSubtask1=true;
bool isSubtask2=true;
int n;
bool isCycle(){
	for(auto x:adj){
		if(x.second.size()<=1)return false;
		if(x.second.size()>2)isSubtask1=false;
	}
	return true;
}
void init(int N, int M,std::vector<int> U, std::vector<int> V, std::vector<int> W) {
	n=N;
	for(int i=0;i<M;i++){
		int x=U[i];
		int y=V[i];
		int z=W[i];
		ms.insert(z);
		edwt[{min(x,y),max(x,y)}]=z;
		SUBTASK1=max(SUBTASK1,(W[i]));
		if(x!=0)isSubtask2=false;
		adj[x].insert(y);
		adj[y].insert(x);
	}
	isCyc=isCycle();
}

vector<int> dijkstra(int s) {
	vector<int> d;
    d.assign(n, LONG_MAX);
    vector<bool> u(n, false);

    d[s] = 0;
    for (int i = 0; i < n; i++) {
        int v = -1;
        for (int j = 0; j < n; j++) {
            if (!u[j] && (v == -1 || d[j] < d[v]))
                v = j;
        }

        if (d[v] == LONG_MAX)
            break;

        u[v] = true;
        for (auto x : adj[v]) {
            int to  = x;
			int wt = edwt[{min(x,v),max(x,v)}];
            if (max(d[v],wt) < d[to]) {
                d[to] = max(d[v],wt);
            }
        }
    }
    return d;
}

int getMinimumFuelCapacity(int X, int Y) {
	if(isSubtask1){
		if(isCyc){
			return SUBTASK1;
		}else
			return -1;
	}else if(isSubtask2){
		if(ms.size()<=2){
			return -1;
		}
		if(X==0){
			int two = edwt[{0,Y}];
			int res=two;
			ms.erase(ms.find(two));
			auto temp = ms.begin();
			res=max(res,(*temp));
			temp++;
			res=max(res,(*temp));
			ms.insert(two);
			return res;
		}
		int one = edwt[{0,X}];
		int two = edwt[{0,Y}];
		int res=max(one,two);
		ms.erase(ms.find(one));
		ms.erase(ms.find(two));
		if(ms.size()>0)
			res=max(res,(*ms.begin()));
		ms.insert(one);
		ms.insert(two);
		return res;
	}else{
		auto res = dijkstra(X);
		return res[Y];
	}
}

Compilation message (stderr)

swap.cpp: In function 'std::vector<int> dijkstra(int)':
swap.cpp:36:17: warning: overflow in conversion from 'long int' to 'std::vector<int>::value_type' {aka 'int'} changes value from '9223372036854775807' to '-1' [-Woverflow]
   36 |     d.assign(n, LONG_MAX);
      |                 ^~~~~~~~

• Subtask 1: 6 / 6
• Subtask 2: 7 / 7
• Subtask 3: 0 / 17
• Subtask 4: 0 / 20
• Subtask 5: 0 / 23
• Subtask 6: 0 / 27