oj.uz

Submission #982353

# Submission time Handle Problem Language Result Execution time Memory
982353 2024-05-14T07:14:36 Z simona1230 Swapping Cities (APIO20_swap) C++17
13 / 100
 132 ms 23964 KB 
#include "swap.h"
#include <bits/stdc++.h>
using namespace std;

int maxx,minn,maxw;
int n,m,x,y;
vector<int> v[100001],w[100001],num[100001];
pair<int,int> p[100001];
bool sec=1;

struct edge
{
    int x,d;
    edge(){}
    edge(int _x,int _d)
    {
        x=_x;
        d=_d;
    }

    bool operator<(const edge&e)const
    {
        return e.d<d;
    }
};

void init(int N, int M,std::vector<int> U, std::vector<int> V, std::vector<int> W)
{
    minn=N;
    n=N;
    m=M;
    for(int i=0;i<m;i++)
    {
        if(U[i]!=0)sec=0;
        maxw=max(maxw,W[i]);
        v[U[i]].push_back(V[i]);
        v[V[i]].push_back(U[i]);
        w[U[i]].push_back(W[i]);
        w[V[i]].push_back(W[i]);
        num[U[i]].push_back(i);
        num[V[i]].push_back(i);
        maxx=max(maxx,(int)v[U[i]].size());
        maxx=max(maxx,(int)v[V[i]].size());
        p[i]={W[i],V[i]};
    }
    sort(p,p+m);

    for(int i=0;i<n;i++)
    {
        minn=min(minn,(int)v[i].size());
    }
}

int getMinimumFuelCapacity(int X, int Y)
{
    x=X;
    y=Y;
    if(maxx<=2)
    {
        if(minn==1)return -1;
        return maxw;
    }

    if(sec)
    {
        if(x==0||y==0)
        {
            if(x>y)swap(x,y);
            int i1=0,i2=1;
            if(p[0].second==y)i1=2;
            if(p[1].second==y)i2=2;
            int ans=max(p[i1].first,p[i2].first);
            ans=max(ans,w[y][0]);
            return ans;
        }
        int ans=p[0].first;
        if(p[0].second==x||p[0].second==y)ans=p[1].first;
        if(p[1].second==x||p[1].second==y)ans=p[2].first;
        ans=max(ans,w[x][0]);
        ans=max(ans,w[y][0]);
        return ans;
    }
}
/*
5 4
0 1 1
0 2 2
0 3 3
0 4 4
4
0 1
0 2
0 3
0 4

*/

Compilation message

swap.cpp: In function 'int getMinimumFuelCapacity(int, int)':
swap.cpp:83:1: warning: control reaches end of non-void function [-Wreturn-type]
   83 | }
      | ^

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8028 KB Output is correct
2 Correct 2 ms 8028 KB Output is correct
3 Correct 2 ms 8028 KB Output is correct
4 Correct 2 ms 8028 KB Output is correct
5 Correct 2 ms 8204 KB Output is correct
6 Correct 3 ms 8028 KB Output is correct
7 Correct 3 ms 8024 KB Output is correct
8 Correct 2 ms 8144 KB Output is correct
9 Correct 52 ms 17236 KB Output is correct
10 Correct 69 ms 19284 KB Output is correct
11 Correct 69 ms 19336 KB Output is correct
12 Correct 88 ms 19796 KB Output is correct
13 Correct 74 ms 19972 KB Output is correct
14 Correct 59 ms 17492 KB Output is correct
15 Correct 110 ms 21212 KB Output is correct
16 Correct 114 ms 20964 KB Output is correct
17 Correct 118 ms 21684 KB Output is correct
18 Correct 118 ms 21684 KB Output is correct
19 Correct 44 ms 13392 KB Output is correct
20 Correct 126 ms 22364 KB Output is correct
21 Correct 118 ms 22284 KB Output is correct
22 Correct 124 ms 22972 KB Output is correct
23 Correct 132 ms 22968 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8028 KB Output is correct
2 Correct 2 ms 8028 KB Output is correct
3 Correct 102 ms 23388 KB Output is correct
4 Correct 103 ms 23964 KB Output is correct
5 Correct 109 ms 23800 KB Output is correct
6 Correct 101 ms 23844 KB Output is correct
7 Correct 108 ms 23820 KB Output is correct
8 Correct 106 ms 23400 KB Output is correct
9 Correct 106 ms 23612 KB Output is correct
10 Correct 104 ms 23272 KB Output is correct

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8028 KB Output is correct
2 Correct 2 ms 8028 KB Output is correct
3 Correct 2 ms 8028 KB Output is correct
4 Correct 2 ms 8028 KB Output is correct
5 Correct 2 ms 8204 KB Output is correct
6 Correct 3 ms 8028 KB Output is correct
7 Correct 3 ms 8024 KB Output is correct
8 Correct 2 ms 8144 KB Output is correct
9 Incorrect 2 ms 8028 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 8028 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8028 KB Output is correct
2 Correct 2 ms 8028 KB Output is correct
3 Correct 2 ms 8028 KB Output is correct
4 Correct 2 ms 8028 KB Output is correct
5 Correct 2 ms 8204 KB Output is correct
6 Correct 3 ms 8028 KB Output is correct
7 Correct 3 ms 8024 KB Output is correct
8 Correct 2 ms 8144 KB Output is correct
9 Correct 52 ms 17236 KB Output is correct
10 Correct 69 ms 19284 KB Output is correct
11 Correct 69 ms 19336 KB Output is correct
12 Correct 88 ms 19796 KB Output is correct
13 Correct 74 ms 19972 KB Output is correct
14 Correct 59 ms 17492 KB Output is correct
15 Correct 110 ms 21212 KB Output is correct
16 Correct 114 ms 20964 KB Output is correct
17 Correct 118 ms 21684 KB Output is correct
18 Correct 118 ms 21684 KB Output is correct
19 Correct 102 ms 23388 KB Output is correct
20 Correct 103 ms 23964 KB Output is correct
21 Correct 109 ms 23800 KB Output is correct
22 Correct 101 ms 23844 KB Output is correct
23 Correct 108 ms 23820 KB Output is correct
24 Correct 106 ms 23400 KB Output is correct
25 Correct 106 ms 23612 KB Output is correct
26 Correct 104 ms 23272 KB Output is correct
27 Incorrect 3 ms 8028 KB Output isn't correct
28 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 8028 KB Output isn't correct
2 Halted 0 ms 0 KB -