oj.uz

Submission #548365

# Submission time Handle Problem Language Result Execution time Memory
548365 2022-04-13T06:40:30 Z ToroTN Swapping Cities (APIO20_swap) C++14
13 / 100
 2000 ms 14040 KB 
#include<bits/stdc++.h>
using namespace std;
#include "swap.h"
#define X first
#define Y second
#define pb push_back

int n,m,dg[100005],u_i,v_i,w_i,x,y,type=-1,flag=-1;
int deter=2,d[1005][1005],st,md,ed,u1,u2,w,node;
vector<pair<int,int> > g[100005];
vector<pair<int,pair<int,int> > > v;
queue<pair<int,int> > q;

void init(int N, int M,
          std::vector<int> U, std::vector<int> V, std::vector<int> W)
{
    n=N;
    m=M;
    for(int i=0;i<m;i++)
    {
        u_i=U[i]+1;
        v_i=V[i]+1;
        w_i=W[i];
        g[u_i].pb({v_i,w_i});
        g[v_i].pb({u_i,w_i});
        ++dg[u_i];
        ++dg[v_i];
        v.push_back({w_i,{u_i,v_i}});
        if(u_i!=1)flag=0;
    }
    sort(v.begin(),v.end());
    for(int i=1;i<=n;i++)
    {
        if(dg[i]>2)
        {
            type=0;
        }
    }
    if(type==-1)
    {
        deter=0;
        for(int i=1;i<=n;i++)if(dg[i]!=2)deter=-1;
    }
}

int getMinimumFuelCapacity(int X, int Y)
{
    x=X+1;
    y=Y+1;
    if(type==-1)
    {
        if(deter==0)return v[v.size()-1].X;
        return -1;
    }
    if(m==n-1&&flag==-1)
    {
        if(m<=2)return -1;
        if(x==1)
        {
            if(g[y][0].Y>v[2].X)return g[y][0].Y;
            return v[2].X;
        }
        if(x==v[0].Y.Y&&y==v[1].Y.Y||x==v[1].Y.Y&&y==v[0].Y.Y)return v[2].X;
        return max(g[x][0].Y,g[y][0].Y);
    }
    if(n<=1000&&m<=2000)
    {
        st=0;
        ed=1e9;
        //printf("%d %d\n",x,y);
        while(ed>=st)
        {
            md=(st+ed)/2;
            //printf("%d %d %d\n",st,md,ed);
            memset(d,0,sizeof d);
            d[x][y]=1;
            q.push({x,y});
            while(!q.empty())
            {
                u1=q.front().X;
                u2=q.front().Y;
                //printf("%d %d\n",u1,u2);
                q.pop();
                for(int i=0;i<g[u1].size();i++)
                {
                    node=g[u1][i].X;
                    w=g[u1][i].Y;
                    if(md>=w&&node!=u2&&d[node][u2]==0)
                    {
                        d[node][u2]=1;
                        q.push({node,u2});
                    }
                }
                for(int i=0;i<g[u2].size();i++)
                {
                    node=g[u2][i].X;
                    w=g[u2][i].Y;
                    if(md>=w&&node!=u1&&d[u1][node]==0)
                    {
                        d[u1][node]=1;
                        q.push({u1,node});
                    }
                }
            }
            if(d[y][x]==1)
            {
                ed=md-1;
            }else
            {
                st=md+1;
            }
        }
        return st;
    }
}

Compilation message

swap.cpp: In function 'int getMinimumFuelCapacity(int, int)':
swap.cpp:63:23: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   63 |         if(x==v[0].Y.Y&&y==v[1].Y.Y||x==v[1].Y.Y&&y==v[0].Y.Y)return v[2].X;
      |                       ^
swap.cpp:84:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   84 |                 for(int i=0;i<g[u1].size();i++)
      |                             ~^~~~~~~~~~~~~
swap.cpp:94:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   94 |                 for(int i=0;i<g[u2].size();i++)
      |                             ~^~~~~~~~~~~~~
swap.cpp:115:1: warning: control reaches end of non-void function [-Wreturn-type]
  115 | }
      | ^

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 2 ms 2596 KB Output is correct
3 Correct 3 ms 2656 KB Output is correct
4 Correct 3 ms 2664 KB Output is correct
5 Correct 3 ms 2644 KB Output is correct
6 Correct 3 ms 2644 KB Output is correct
7 Correct 4 ms 2644 KB Output is correct
8 Correct 2 ms 2644 KB Output is correct
9 Correct 45 ms 9540 KB Output is correct
10 Correct 58 ms 10452 KB Output is correct
11 Correct 62 ms 10476 KB Output is correct
12 Correct 68 ms 10632 KB Output is correct
13 Correct 57 ms 10612 KB Output is correct
14 Correct 48 ms 9904 KB Output is correct
15 Correct 152 ms 12220 KB Output is correct
16 Correct 103 ms 12072 KB Output is correct
17 Correct 118 ms 12516 KB Output is correct
18 Correct 114 ms 12420 KB Output is correct
19 Correct 57 ms 8260 KB Output is correct
20 Correct 129 ms 13076 KB Output is correct
21 Correct 106 ms 13132 KB Output is correct
22 Correct 127 ms 13608 KB Output is correct
23 Correct 112 ms 13592 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 2 ms 2596 KB Output is correct
3 Correct 103 ms 14040 KB Output is correct
4 Correct 104 ms 13824 KB Output is correct
5 Correct 107 ms 13832 KB Output is correct
6 Correct 104 ms 13660 KB Output is correct
7 Correct 105 ms 13840 KB Output is correct
8 Correct 104 ms 13544 KB Output is correct
9 Correct 109 ms 13688 KB Output is correct
10 Correct 104 ms 13552 KB Output is correct

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 2 ms 2596 KB Output is correct
3 Correct 3 ms 2656 KB Output is correct
4 Correct 3 ms 2664 KB Output is correct
5 Correct 3 ms 2644 KB Output is correct
6 Correct 3 ms 2644 KB Output is correct
7 Correct 4 ms 2644 KB Output is correct
8 Correct 2 ms 2644 KB Output is correct
9 Correct 12 ms 6496 KB Output is correct
10 Correct 1165 ms 6868 KB Output is correct
11 Execution timed out 2083 ms 6612 KB Time limit exceeded
12 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 6496 KB Output is correct
2 Correct 2 ms 2644 KB Output is correct
3 Correct 2 ms 2596 KB Output is correct
4 Correct 3 ms 2656 KB Output is correct
5 Correct 3 ms 2664 KB Output is correct
6 Correct 3 ms 2644 KB Output is correct
7 Correct 3 ms 2644 KB Output is correct
8 Correct 4 ms 2644 KB Output is correct
9 Correct 2 ms 2644 KB Output is correct
10 Correct 45 ms 9540 KB Output is correct
11 Correct 58 ms 10452 KB Output is correct
12 Correct 62 ms 10476 KB Output is correct
13 Correct 68 ms 10632 KB Output is correct
14 Correct 57 ms 10612 KB Output is correct
15 Correct 1165 ms 6868 KB Output is correct
16 Execution timed out 2083 ms 6612 KB Time limit exceeded
17 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 2 ms 2596 KB Output is correct
3 Correct 3 ms 2656 KB Output is correct
4 Correct 3 ms 2664 KB Output is correct
5 Correct 3 ms 2644 KB Output is correct
6 Correct 3 ms 2644 KB Output is correct
7 Correct 4 ms 2644 KB Output is correct
8 Correct 2 ms 2644 KB Output is correct
9 Correct 45 ms 9540 KB Output is correct
10 Correct 58 ms 10452 KB Output is correct
11 Correct 62 ms 10476 KB Output is correct
12 Correct 68 ms 10632 KB Output is correct
13 Correct 57 ms 10612 KB Output is correct
14 Correct 48 ms 9904 KB Output is correct
15 Correct 152 ms 12220 KB Output is correct
16 Correct 103 ms 12072 KB Output is correct
17 Correct 118 ms 12516 KB Output is correct
18 Correct 114 ms 12420 KB Output is correct
19 Correct 103 ms 14040 KB Output is correct
20 Correct 104 ms 13824 KB Output is correct
21 Correct 107 ms 13832 KB Output is correct
22 Correct 104 ms 13660 KB Output is correct
23 Correct 105 ms 13840 KB Output is correct
24 Correct 104 ms 13544 KB Output is correct
25 Correct 109 ms 13688 KB Output is correct
26 Correct 104 ms 13552 KB Output is correct
27 Correct 1165 ms 6868 KB Output is correct
28 Execution timed out 2083 ms 6612 KB Time limit exceeded
29 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 6496 KB Output is correct
2 Correct 2 ms 2644 KB Output is correct
3 Correct 2 ms 2596 KB Output is correct
4 Correct 3 ms 2656 KB Output is correct
5 Correct 3 ms 2664 KB Output is correct
6 Correct 3 ms 2644 KB Output is correct
7 Correct 3 ms 2644 KB Output is correct
8 Correct 4 ms 2644 KB Output is correct
9 Correct 2 ms 2644 KB Output is correct
10 Correct 45 ms 9540 KB Output is correct
11 Correct 58 ms 10452 KB Output is correct
12 Correct 62 ms 10476 KB Output is correct
13 Correct 68 ms 10632 KB Output is correct
14 Correct 57 ms 10612 KB Output is correct
15 Correct 48 ms 9904 KB Output is correct
16 Correct 152 ms 12220 KB Output is correct
17 Correct 103 ms 12072 KB Output is correct
18 Correct 118 ms 12516 KB Output is correct
19 Correct 114 ms 12420 KB Output is correct
20 Correct 103 ms 14040 KB Output is correct
21 Correct 104 ms 13824 KB Output is correct
22 Correct 107 ms 13832 KB Output is correct
23 Correct 104 ms 13660 KB Output is correct
24 Correct 105 ms 13840 KB Output is correct
25 Correct 104 ms 13544 KB Output is correct
26 Correct 109 ms 13688 KB Output is correct
27 Correct 104 ms 13552 KB Output is correct
28 Correct 1165 ms 6868 KB Output is correct
29 Execution timed out 2083 ms 6612 KB Time limit exceeded
30 Halted 0 ms 0 KB -