| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 371606 |
2021-02-27T02:50:26 Z |
Dymo |
Olympic Bus (JOI20_ho_t4) |
C++14 |
|
35 ms |
13548 KB |
#pragma GCC optimize("Ofast")
#pragma GCC optimization("unroll-loops, no-stack-protector")
#pragma GCC target("avx,avx2,fma")
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ull long long
#define pll pair<ll,ll>
#define ff first
#define ss second
#define pb push_back
//#define endl "\n"
const ll maxn =2e5+30;
const ll mod=1e9+7 ;
const ll base=1e18;
ll x[maxn];
ll y[maxn];
ll c[maxn];
ll d[maxn];
vector<ll> adj[maxn][2];
ll dp[maxn][6];
ll pre[maxn];
ll n, m ;
bool dd[maxn];
bool in[maxn];
void dosth(ll p,ll type,ll ta,ll rc,ll t)
{
/* priority_queue<pll,vector<pll>,greater<pll>> q;
for (int i=1; i<=n; i++)
{
dp[i][type]=base;
}
dp[p][type]=0;
q.push(make_pair(dp[p][type],p));
while (!q.empty())
{
auto p=q.top();
q.pop();
ll u=p.ss;
if (dp[u][type]!=p.ff)
continue;
for (auto to:adj[u][ta])
{
if (u==rc&&to==t)
continue;
ll nxt=x[to]+y[to]-u;
if (dp[nxt][type]>dp[u][type]+c[to])
{
dp[nxt][type]=dp[u][type]+c[to];
q.push(make_pair(dp[nxt][type],nxt));
pre[nxt]=to;
}
}
}*/
for (int i=1; i<=n; i++)
{
dp[i][type]=base;
in[i]=0;
}
dp[p][type]=0;
for (int i=1; i<=n; i++)
{
ll min_d=base;
ll minnd=1;
for (int i=1; i<=n; i++)
{
if (in[i])
continue;
if (dp[i][type]<=min_d)
{
min_d=dp[i][type];
minnd=i;
}
}
dd[minnd]=1;
for (auto to:adj[minnd][ta])
{
if (minnd==rc&&to==t)
continue;
ll nxt= x[to]+y[to]-minnd;
if (dp[nxt][type]>dp[minnd][type]+c[to])
{
dp[nxt][type]=dp[minnd][type]+c[to];
pre[nxt]=to;
}
}
}
}
ll ans=base;
void dosth1()
{
dosth(1,0,0,-1,-1);
ll nw=n;
while (nw!=1)
{
// cout <<nw<<" "<<pre[nw]<<endl;
dd[pre[nw]]=1;
// cout <<pre[nw]<<endl;
nw=x[pre[nw]]+y[pre[nw]]-nw;
}
dosth(1,1,1,-1,-1);
dosth(n,2,0,-1,-1);
dosth(n,3,1,-1,-1);
ans=min(ans,dp[n][0]+dp[n][1]);
for (int i=1; i<=m; i++)
{
if (dd[i])
{
ll h1=x[i];
ll h2=y[i];
adj[h2][0].pb(i);
swap(x[i],y[i]);
dosth(1,4,0,h1,i);
ll h=dp[n][4]+d[i];
dosth(n,4,0,h1,i);
h+=dp[1][4];
swap(x[i],y[i]);
adj[h2][0].pop_back();
ans=min(ans,h);
}
else
{
ans=min(ans,dp[n][0]+dp[x[i]][1]+dp[y[i]][2]+c[i]+d[i]);
/* if (i==2)
{
cout <<min(dp[n][0],dp[y[i]][0]+dp[x[i]][3]+c[i])+dp[x[i]][1]+dp[y[i]][2]+c[i]+d[i]<<endl;
}*/
/* if (min(dp[n][0],dp[y[i]][0]+dp[x[i]][3])+dp[x[i]][1]+dp[y[i]][2]+c[i]+d[i]==1)
{
cout <<i<<endl;
}*/
}
}
}
void change()
{
for (int i=1; i<=n; i++)
{
adj[i][0].clear();
adj[i][1].clear();
}
for (int i=1; i<=m; i++)
{
if (x[i]==n)
x[i]=1;
else if (x[i]==1)
x[i]=n;
if (y[i]==n)
y[i]=1;
else if (y[i]==1)
y[i]=n;
// cout <<x[i]<< " "<<y[i]<<endl;
adj[x[i]][0].pb(i);
adj[y[i]][1].pb(i);
}
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
if (fopen("t.inp","r"))
{
freopen("test.inp","r",stdin);
freopen("test.out","w",stdout);
}
cin>> n>> m;
for (int i=1; i<=m; i++)
{
cin>>x[i]>> y[i]>>c[i]>> d[i ];
adj[x[i]][0].pb(i);
adj[y[i]][1].pb(i);
}
dosth(1,0,0,-1,-1);
dosth(n,1,0,-1,-1);
// cout <<dp[n][0]<<" "<<dp[1][1]<<endl;
if (dp[n][0]!=base&&dp[1][1]!=base)
{
// cout <<"?"<< " "<<endl;
dosth1();
change();
dosth1();
if (ans>=base)
{
ans=-1;
}
cout <<ans<<endl;
}
else if (dp[n][0]!=base)
{
dosth1();
if (ans>=base)
{
ans=-1;
}
cout <<ans<<endl;
}
else if (dp[1][1]!=base)
{
change();
dosth1();
if (ans>=base)
{
ans=-1;
}
cout <<ans<<endl;
}
else
{
dosth(1,0,0,-1,-1);
dosth(1,1,1,-1,-1);
dosth(n,2,0,-1,-1);
dosth(n,3,1,-1,-1);
ll ans=dp[n][0]+dp[n][1];
for (int i=1; i<=m; i++)
{
ans=min(ans,dp[y[i]][0]+dp[x[i]][3]+dp[y[i]][2]+dp[x[i]][1]+d[i]+2*c[i]);
}
if (ans>=base)
{
ans=-1;
}
cout <<ans;
}
}
Compilation message
ho_t4.cpp:2: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
2 | #pragma GCC optimization("unroll-loops, no-stack-protector")
|
ho_t4.cpp: In function 'int main()':
ho_t4.cpp:175:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
175 | freopen("test.inp","r",stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
ho_t4.cpp:176:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
176 | freopen("test.out","w",stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
9 ms |
9964 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
35 ms |
13548 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
8 ms |
9836 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
9 ms |
9964 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
