Submission #364479

#	Time	Username	Problem	Language	Result	Execution time	Memory
364479		cpp219	Olympic Bus (JOI20_ho_t4)	C++14	0 / 100	1083 ms	6764 KiB

ho_t4

#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")

#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define fs first
#define sc second
using namespace std;
const ll N = 200 + 6;
const ll inf = 1e16 + 7;
typedef pair<int,int> LL;

struct edge{
    ll v,c,id;
};
vector<edge> g[N],rg[N];
ll n,m,u,v,c,inv,d[N],D[4][N],ans = inf,banned;
bool dd[N],spec[N][N];
void cond_to_all(ll scr,ll cond){
    memset(dd,0,sizeof(dd)); fill(d,d + n + 1,inf);
    d[scr] = 0;
    while(1){
        ll x = inf,u = -1;
        for (ll i = 1;i <= n;i++) if (d[i] < x && !dd[i]) x = d[i],u = i;
        if (u == -1) break; dd[u] = 1;
        for (auto i : g[u]){
            ll v = i.v,L = i.c;
            if (d[v] > d[u] + L && i.id != banned) d[v] = d[u] + L,spec[u][v] = 1,spec[v][u] = 0;
        }
    }
    for (ll i = 1;i <= n;i++) D[cond][i] = d[i];
}

void all_to_cond(ll scr,ll cond){
    memset(dd,0,sizeof(dd)); fill(d,d + n + 1,inf);
    d[scr] = 0;
    while(1){
        ll x = inf,u = -1;
        for (ll i = 1;i <= n;i++) if (d[i] < x && !dd[i]) x = d[i],u = i;
        if (u == -1) break; dd[u] = 1;
        for (auto i : rg[u]){
            ll v = i.v,L = i.c;
            if (d[v] > d[u] + L && i.id != banned) d[v] = d[u] + L,spec[v][u] = 1,spec[u][v] = 0;
        }
    }
    for (ll i = 1;i <= n;i++) D[cond][i] = d[i];
}

struct Road{
    ll u,v,c,inv;
};
Road a[100000];

void Rev(ll id){
    banned = id;
    u = a[id].u; v = a[id].v; c = a[id].c;
    g[v].push_back({u,c,m + 1}); rg[u].push_back({v,c,m + 1});
    cond_to_all(1,0); cond_to_all(n,2); all_to_cond(1,1); all_to_cond(n,3);
    ans = min(ans,D[0][n] + D[2][1] + a[id].inv);
    g[v].pop_back(); rg[u].pop_back(); banned = 0;
    cond_to_all(1,0); cond_to_all(n,2); all_to_cond(1,1); all_to_cond(n,3);
}
/// 0 : 1 to all    1 : all to 1    2 : n to all    3 : all to n
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    #define task "tst"
    if (fopen(task".INP","r")){
        freopen(task".INP","r",stdin);
        //freopen(task".OUT","w",stdout);
    }
    cin>>n>>m;
    for (ll i = 1;i <= m;i++){
        cin>>u>>v>>c>>inv; a[i] = {u,v,c,inv};
        g[u].push_back({v,c,i}); rg[v].push_back({u,c,i});
    }
    cond_to_all(1,0); cond_to_all(n,2); all_to_cond(1,1); all_to_cond(n,3);
    ans = D[0][n] + D[2][1];
    for (ll i = 1;i <= m;i++){
        u = a[i].u; v = a[i].v; c = a[i].c;
        if (!spec[u][v]){
            //cout<<D[2][1]; return 0;
            ll p = min(D[0][n],D[0][v] + c + D[3][u]),q = min(D[2][1],D[2][v] + c + D[1][u]);
            ans = min(ans,p + q + a[i].inv); //cout<<p<<" x "<<D[2][v]; return 0;
        }
        else Rev(i);
    }
    cout<<(ans >= inf ? -1 : ans);
}

Compilation message (stderr)

ho_t4.cpp:2: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
    2 | #pragma GCC optimization ("O3")
      | 
ho_t4.cpp:3: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
    3 | #pragma GCC optimization ("unroll-loops")
      | 
ho_t4.cpp: In function 'void cond_to_all(long long int, long long int)':
ho_t4.cpp:27:9: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   27 |         if (u == -1) break; dd[u] = 1;
      |         ^~
ho_t4.cpp:27:29: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   27 |         if (u == -1) break; dd[u] = 1;
      |                             ^~
ho_t4.cpp: In function 'void all_to_cond(long long int, long long int)':
ho_t4.cpp:42:9: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   42 |         if (u == -1) break; dd[u] = 1;
      |         ^~
ho_t4.cpp:42:29: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   42 |         if (u == -1) break; dd[u] = 1;
      |                             ^~
ho_t4.cpp: In function 'int main()':
ho_t4.cpp:71:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   71 |         freopen(task".INP","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 5
• Subtask 2: 0 / 11
• Subtask 3: 0 / 21
• Subtask 4: 0 / 63