oj.uz

Submission #982357

# Submission time Handle Problem Language Result Execution time Memory
982357 2024-05-14T07:21:24 Z simona1230 Swapping Cities (APIO20_swap) C++17
13 / 100
 130 ms 25836 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,y,d;
    edge(){}
    edge(int _x,int _y,int _d)
    {
        x=_x;
        y=_y;
        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 d[1024][1024];
void dijkstra()
{
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<n;j++)
        {
            d[i][j]=1e9+1;
        }
    }

    priority_queue<edge> q;

    q.push({x,y,0});
    d[x][y]=0;

    while(q.size())
    {
        edge e=q.top();
        q.pop();

        if(d[e.x][e.y]>=e.d)
        {
            for(int i=0;i<v[e.x].size();i++)
            {
                for(int j=0;j<v[e.y].size();j++)
                {
                    int nb1=v[e.x][i],nb2=v[e.y][j];
                    if(num[e.x][i]==num[e.y][j]||nb1==nb2)continue;

                    int wg=max(w[e.x][i],w[e.y][j]);
                    if(d[nb1][nb2]>=max(d[e.x][e.y],wg))
                    {
                        d[nb1][nb2]=max(d[e.x][e.y],wg);
                        q.push({nb1,nb2,d[nb1][nb2]});
                    }
                }
            }
        }
    }
}

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;
    }

    int ans=d[y][x];
    if(ans==1e9+1)ans=-1;
    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 'void dijkstra()':
swap.cpp:78:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   78 |             for(int i=0;i<v[e.x].size();i++)
      |                         ~^~~~~~~~~~~~~~
swap.cpp:80:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   80 |                 for(int j=0;j<v[e.y].size();j++)
      |                             ~^~~~~~~~~~~~~~

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 10076 KB Output is correct
2 Correct 2 ms 10076 KB Output is correct
3 Correct 3 ms 10076 KB Output is correct
4 Correct 3 ms 10076 KB Output is correct
5 Correct 3 ms 10076 KB Output is correct
6 Correct 3 ms 10076 KB Output is correct
7 Correct 3 ms 10076 KB Output is correct
8 Correct 3 ms 10072 KB Output is correct
9 Correct 51 ms 19284 KB Output is correct
10 Correct 70 ms 21332 KB Output is correct
11 Correct 69 ms 20980 KB Output is correct
12 Correct 77 ms 21844 KB Output is correct
13 Correct 74 ms 21792 KB Output is correct
14 Correct 54 ms 19392 KB Output is correct
15 Correct 112 ms 23260 KB Output is correct
16 Correct 110 ms 22788 KB Output is correct
17 Correct 113 ms 23480 KB Output is correct
18 Correct 115 ms 23444 KB Output is correct
19 Correct 44 ms 15512 KB Output is correct
20 Correct 113 ms 24276 KB Output is correct
21 Correct 130 ms 24296 KB Output is correct
22 Correct 117 ms 24932 KB Output is correct
23 Correct 114 ms 25016 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 10076 KB Output is correct
2 Correct 2 ms 10076 KB Output is correct
3 Correct 99 ms 25180 KB Output is correct
4 Correct 108 ms 25748 KB Output is correct
5 Correct 104 ms 25660 KB Output is correct
6 Correct 98 ms 25632 KB Output is correct
7 Correct 114 ms 25836 KB Output is correct
8 Correct 97 ms 25316 KB Output is correct
9 Correct 102 ms 25540 KB Output is correct
10 Correct 104 ms 25372 KB Output is correct

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 10076 KB Output is correct
2 Correct 2 ms 10076 KB Output is correct
3 Correct 3 ms 10076 KB Output is correct
4 Correct 3 ms 10076 KB Output is correct
5 Correct 3 ms 10076 KB Output is correct
6 Correct 3 ms 10076 KB Output is correct
7 Correct 3 ms 10076 KB Output is correct
8 Correct 3 ms 10072 KB Output is correct
9 Incorrect 2 ms 10076 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 10076 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 10076 KB Output is correct
2 Correct 2 ms 10076 KB Output is correct
3 Correct 3 ms 10076 KB Output is correct
4 Correct 3 ms 10076 KB Output is correct
5 Correct 3 ms 10076 KB Output is correct
6 Correct 3 ms 10076 KB Output is correct
7 Correct 3 ms 10076 KB Output is correct
8 Correct 3 ms 10072 KB Output is correct
9 Correct 51 ms 19284 KB Output is correct
10 Correct 70 ms 21332 KB Output is correct
11 Correct 69 ms 20980 KB Output is correct
12 Correct 77 ms 21844 KB Output is correct
13 Correct 74 ms 21792 KB Output is correct
14 Correct 54 ms 19392 KB Output is correct
15 Correct 112 ms 23260 KB Output is correct
16 Correct 110 ms 22788 KB Output is correct
17 Correct 113 ms 23480 KB Output is correct
18 Correct 115 ms 23444 KB Output is correct
19 Correct 99 ms 25180 KB Output is correct
20 Correct 108 ms 25748 KB Output is correct
21 Correct 104 ms 25660 KB Output is correct
22 Correct 98 ms 25632 KB Output is correct
23 Correct 114 ms 25836 KB Output is correct
24 Correct 97 ms 25316 KB Output is correct
25 Correct 102 ms 25540 KB Output is correct
26 Correct 104 ms 25372 KB Output is correct
27 Incorrect 3 ms 10076 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 10076 KB Output isn't correct
2 Halted 0 ms 0 KB -