oj.uz

Submission #982377

# Submission time Handle Problem Language Result Execution time Memory
982377 2024-05-14T07:41:26 Z simona1230 Swapping Cities (APIO20_swap) C++17
30 / 100
 1764 ms 51936 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();
        //cout<<e.x<<" "<<e.y<<" "<<e.d<<endl;

        if(d[e.x][e.y]>=e.d)
        {
            for(int i=0; i<v[e.x].size(); i++)
            {
                int nb1=v[e.x][i];
                //cout<<nb1<<"-"<<e.y<<endl;
                if(nb1!=e.y)
                {
                    if(d[nb1][e.y]>max(d[e.x][e.y],w[e.x][i]))
                    {
                        //cout<<"in"<<endl;
                        d[nb1][e.y]=max(d[e.x][e.y],w[e.x][i]);
                        q.push({nb1,e.y,d[nb1][e.y]});
                    }
                }
            }

            for(int j=0; j<v[e.y].size(); j++)
            {
                int nb2=v[e.y][j];
                if(nb2!=e.x)
                {
                    if(d[e.x][nb2]>max(d[e.x][e.y],w[e.y][j]))
                    {
                        d[e.x][nb2]=max(d[e.x][e.y],w[e.y][j]);
                        q.push({e.x,nb2,d[e.x][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;
    }

    dijkstra();
    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:79:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   79 |             for(int i=0; i<v[e.x].size(); i++)
      |                          ~^~~~~~~~~~~~~~
swap.cpp:94:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   94 |             for(int j=0; j<v[e.y].size(); j++)
      |                          ~^~~~~~~~~~~~~~

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 2 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 10156 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 10076 KB Output is correct
9 Correct 51 ms 19284 KB Output is correct
10 Correct 76 ms 21332 KB Output is correct
11 Correct 74 ms 21300 KB Output is correct
12 Correct 72 ms 21840 KB Output is correct
13 Correct 83 ms 21840 KB Output is correct
14 Correct 58 ms 19280 KB Output is correct
15 Correct 118 ms 23052 KB Output is correct
16 Correct 116 ms 22788 KB Output is correct
17 Correct 137 ms 23436 KB Output is correct
18 Correct 118 ms 23480 KB Output is correct
19 Correct 46 ms 15456 KB Output is correct
20 Correct 117 ms 24276 KB Output is correct
21 Correct 118 ms 24128 KB Output is correct
22 Correct 117 ms 24992 KB Output is correct
23 Correct 117 ms 25016 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10076 KB Output is correct
2 Correct 2 ms 10076 KB Output is correct
3 Correct 101 ms 25300 KB Output is correct
4 Correct 105 ms 25864 KB Output is correct
5 Correct 135 ms 25836 KB Output is correct
6 Correct 101 ms 25632 KB Output is correct
7 Correct 105 ms 25724 KB Output is correct
8 Correct 119 ms 25312 KB Output is correct
9 Correct 104 ms 25664 KB Output is correct
10 Correct 99 ms 25068 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 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 10156 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 10076 KB Output is correct
9 Correct 3 ms 10072 KB Output is correct
10 Correct 387 ms 23700 KB Output is correct
11 Correct 331 ms 18580 KB Output is correct
12 Correct 331 ms 18212 KB Output is correct
13 Correct 260 ms 17684 KB Output is correct
14 Correct 324 ms 17704 KB Output is correct
15 Correct 357 ms 23348 KB Output is correct
16 Correct 298 ms 19920 KB Output is correct
17 Correct 309 ms 17936 KB Output is correct
18 Correct 432 ms 22696 KB Output is correct
19 Correct 336 ms 24784 KB Output is correct
20 Correct 348 ms 20168 KB Output is correct
21 Correct 701 ms 23368 KB Output is correct
22 Correct 158 ms 17776 KB Output is correct
23 Correct 376 ms 17732 KB Output is correct
24 Correct 1511 ms 36772 KB Output is correct
25 Correct 1132 ms 32772 KB Output is correct
26 Correct 1764 ms 51936 KB Output is correct
27 Correct 315 ms 18484 KB Output is correct
28 Correct 1416 ms 36804 KB Output is correct

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 10072 KB Output is correct
2 Correct 2 ms 10076 KB Output is correct
3 Correct 2 ms 10076 KB Output is correct
4 Correct 3 ms 10076 KB Output is correct
5 Correct 3 ms 10156 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 10076 KB Output is correct
9 Correct 3 ms 10076 KB Output is correct
10 Correct 51 ms 19284 KB Output is correct
11 Correct 76 ms 21332 KB Output is correct
12 Correct 74 ms 21300 KB Output is correct
13 Correct 72 ms 21840 KB Output is correct
14 Correct 83 ms 21840 KB Output is correct
15 Correct 387 ms 23700 KB Output is correct
16 Correct 331 ms 18580 KB Output is correct
17 Correct 331 ms 18212 KB Output is correct
18 Correct 260 ms 17684 KB Output is correct
19 Correct 324 ms 17704 KB Output is correct
20 Correct 357 ms 23348 KB Output is correct
21 Correct 298 ms 19920 KB Output is correct
22 Correct 309 ms 17936 KB Output is correct
23 Correct 432 ms 22696 KB Output is correct
24 Correct 336 ms 24784 KB Output is correct
25 Correct 348 ms 20168 KB Output is correct
26 Correct 701 ms 23368 KB Output is correct
27 Correct 158 ms 17776 KB Output is correct
28 Correct 376 ms 17732 KB Output is correct
29 Correct 1511 ms 36772 KB Output is correct
30 Correct 1132 ms 32772 KB Output is correct
31 Correct 1764 ms 51936 KB Output is correct
32 Correct 315 ms 18484 KB Output is correct
33 Correct 1416 ms 36804 KB Output is correct
34 Runtime error 44 ms 27732 KB Execution killed with signal 11
35 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 2 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 10156 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 10076 KB Output is correct
9 Correct 51 ms 19284 KB Output is correct
10 Correct 76 ms 21332 KB Output is correct
11 Correct 74 ms 21300 KB Output is correct
12 Correct 72 ms 21840 KB Output is correct
13 Correct 83 ms 21840 KB Output is correct
14 Correct 58 ms 19280 KB Output is correct
15 Correct 118 ms 23052 KB Output is correct
16 Correct 116 ms 22788 KB Output is correct
17 Correct 137 ms 23436 KB Output is correct
18 Correct 118 ms 23480 KB Output is correct
19 Correct 101 ms 25300 KB Output is correct
20 Correct 105 ms 25864 KB Output is correct
21 Correct 135 ms 25836 KB Output is correct
22 Correct 101 ms 25632 KB Output is correct
23 Correct 105 ms 25724 KB Output is correct
24 Correct 119 ms 25312 KB Output is correct
25 Correct 104 ms 25664 KB Output is correct
26 Correct 99 ms 25068 KB Output is correct
27 Correct 387 ms 23700 KB Output is correct
28 Correct 331 ms 18580 KB Output is correct
29 Correct 331 ms 18212 KB Output is correct
30 Correct 260 ms 17684 KB Output is correct
31 Correct 324 ms 17704 KB Output is correct
32 Correct 357 ms 23348 KB Output is correct
33 Correct 298 ms 19920 KB Output is correct
34 Correct 309 ms 17936 KB Output is correct
35 Correct 432 ms 22696 KB Output is correct
36 Runtime error 44 ms 27732 KB Execution killed with signal 11
37 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 10072 KB Output is correct
2 Correct 2 ms 10076 KB Output is correct
3 Correct 2 ms 10076 KB Output is correct
4 Correct 3 ms 10076 KB Output is correct
5 Correct 3 ms 10156 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 10076 KB Output is correct
9 Correct 3 ms 10076 KB Output is correct
10 Correct 51 ms 19284 KB Output is correct
11 Correct 76 ms 21332 KB Output is correct
12 Correct 74 ms 21300 KB Output is correct
13 Correct 72 ms 21840 KB Output is correct
14 Correct 83 ms 21840 KB Output is correct
15 Correct 58 ms 19280 KB Output is correct
16 Correct 118 ms 23052 KB Output is correct
17 Correct 116 ms 22788 KB Output is correct
18 Correct 137 ms 23436 KB Output is correct
19 Correct 118 ms 23480 KB Output is correct
20 Correct 101 ms 25300 KB Output is correct
21 Correct 105 ms 25864 KB Output is correct
22 Correct 135 ms 25836 KB Output is correct
23 Correct 101 ms 25632 KB Output is correct
24 Correct 105 ms 25724 KB Output is correct
25 Correct 119 ms 25312 KB Output is correct
26 Correct 104 ms 25664 KB Output is correct
27 Correct 99 ms 25068 KB Output is correct
28 Correct 387 ms 23700 KB Output is correct
29 Correct 331 ms 18580 KB Output is correct
30 Correct 331 ms 18212 KB Output is correct
31 Correct 260 ms 17684 KB Output is correct
32 Correct 324 ms 17704 KB Output is correct
33 Correct 357 ms 23348 KB Output is correct
34 Correct 298 ms 19920 KB Output is correct
35 Correct 309 ms 17936 KB Output is correct
36 Correct 432 ms 22696 KB Output is correct
37 Runtime error 44 ms 27732 KB Execution killed with signal 11
38 Halted 0 ms 0 KB -