oj.uz

Submission #332476

# Submission time Handle Problem Language Result Execution time Memory
332476 2020-12-02T16:57:01 Z egas Swapping Cities (APIO20_swap) C++14
13 / 100
 1227 ms 43124 KB 
#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

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.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 492 KB Output is correct
5 Correct 2 ms 620 KB Output is correct
6 Correct 2 ms 620 KB Output is correct
7 Correct 2 ms 620 KB Output is correct
8 Correct 2 ms 620 KB Output is correct
9 Correct 286 ms 27116 KB Output is correct
10 Correct 385 ms 33260 KB Output is correct
11 Correct 361 ms 32620 KB Output is correct
12 Correct 415 ms 34668 KB Output is correct
13 Correct 413 ms 34576 KB Output is correct
14 Correct 343 ms 27628 KB Output is correct
15 Correct 450 ms 37496 KB Output is correct
16 Correct 450 ms 36764 KB Output is correct
17 Correct 471 ms 38740 KB Output is correct
18 Correct 465 ms 38608 KB Output is correct
19 Correct 89 ms 10860 KB Output is correct
20 Correct 559 ms 38888 KB Output is correct
21 Correct 483 ms 37800 KB Output is correct
22 Correct 484 ms 40148 KB Output is correct
23 Correct 485 ms 40020 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1153 ms 41192 KB Output is correct
4 Correct 1140 ms 43080 KB Output is correct
5 Correct 1227 ms 42112 KB Output is correct
6 Correct 1122 ms 43124 KB Output is correct
7 Correct 1166 ms 42728 KB Output is correct
8 Correct 1157 ms 41112 KB Output is correct
9 Correct 1126 ms 42216 KB Output is correct
10 Correct 1175 ms 40740 KB Output is correct

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 364 KB Output isn't correct

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 364 KB Output isn't correct

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 492 KB Output is correct
5 Correct 2 ms 620 KB Output is correct
6 Correct 2 ms 620 KB Output is correct
7 Correct 2 ms 620 KB Output is correct
8 Correct 2 ms 620 KB Output is correct
9 Correct 286 ms 27116 KB Output is correct
10 Correct 385 ms 33260 KB Output is correct
11 Correct 361 ms 32620 KB Output is correct
12 Correct 415 ms 34668 KB Output is correct
13 Correct 413 ms 34576 KB Output is correct
14 Correct 343 ms 27628 KB Output is correct
15 Correct 450 ms 37496 KB Output is correct
16 Correct 450 ms 36764 KB Output is correct
17 Correct 471 ms 38740 KB Output is correct
18 Correct 465 ms 38608 KB Output is correct
19 Correct 1153 ms 41192 KB Output is correct
20 Correct 1140 ms 43080 KB Output is correct
21 Correct 1227 ms 42112 KB Output is correct
22 Correct 1122 ms 43124 KB Output is correct
23 Correct 1166 ms 42728 KB Output is correct
24 Correct 1157 ms 41112 KB Output is correct
25 Correct 1126 ms 42216 KB Output is correct
26 Correct 1175 ms 40740 KB Output is correct
27 Incorrect 2 ms 620 KB Output isn't correct
28 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 364 KB Output isn't correct