oj.uz

답안 #466374

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
466374 2021-08-19T04:34:45 Z NhatMinh0208 Olympic Bus (JOI20_ho_t4) C++17
32 / 100
 65 ms 4260 KB 
#ifndef CPL_TEMPLATE
#define CPL_TEMPLATE
/*
	Normie's Template v2.5
	Changes:
    Added warning against using pragmas on USACO.
*/
// Standard library in one include.
#include <bits/stdc++.h>
using namespace std;
 
// ordered_set library.
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
#define ordered_set(el) tree<el,null_type,less<el>,rb_tree_tag,tree_order_statistics_node_update>
 
// AtCoder library. (Comment out these two lines if you're not submitting in AtCoder.) (Or if you want to use it in other judges, run expander.py first.)
//#include <atcoder/all>
//using namespace atcoder;

//Pragmas (Comment out these three lines if you're submitting in szkopul or USACO.)
#pragma comment(linker, "/stack:200000000")
#pragma GCC optimize("Ofast,unroll-loops,tree-vectorize")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
 
//File I/O.
#define FILE_IN "cseq.inp"
#define FILE_OUT "cseq.out"
#define ofile freopen(FILE_IN,"r",stdin);freopen(FILE_OUT,"w",stdout)
 
//Fast I/O.
#define fio ios::sync_with_stdio(0);cin.tie(0)
#define nfio cin.tie(0)
#define endl "\n"
 
//Order checking.
#define ord(a,b,c) ((a>=b)and(b>=c))
 
//min/max redefines, so i dont have to resolve annoying compile errors.
#define min(a,b) (((a)<(b))?(a):(b))
#define max(a,b) (((a)>(b))?(a):(b))

// Fast min/max assigns to use with AVX.
// Requires g++ 9.2.0.
template<typename T>
__attribute__((always_inline)) void chkmin(T& a, const T& b) {
    a=(a<b)?a:b;
}

template<typename T>
__attribute__((always_inline)) void chkmax(T& a, const T& b) {
    a=(a>b)?a:b;
}
 
//Constants.
#define MOD (ll(998244353))
#define MAX 300001
#define mag 320
const long double PI=3.14159265358979;
 
//Pairs and 3-pairs.
#define p1 first
#define p2 second.first
#define p3 second.second
#define fi first
#define se second
#define pii(element_type) pair<element_type,element_type>
#define piii(element_type) pair<element_type,pii(element_type)>
 
//Quick power of 2.
#define pow2(x) (ll(1)<<x)
 
//Short for-loops.
#define ff(i,__,___) for(int i=__;i<=___;i++)
#define rr(i,__,___) for(int i=__;i>=___;i--)
 
//Typedefs.
#define bi BigInt
typedef long long ll;
typedef long double ld;
typedef short sh;

// Binpow and stuff
ll BOW(ll a, ll x, ll p)
{
	if (!x) return 1;
	ll res=BOW(a,x/2,p);
	res*=res;
	res%=p;
	if (x%2) res*=a;
	return res%p;
}
ll INV(ll a, ll p)
{
	return BOW(a,p-2,p);
}
//---------END-------//
#endif
vector<pii(ll)> gt[201];
vector<int> vec,vec2;
ll n,m,i,j,k,t,t1,u,v,a,b,c,res=0;
ll d1[201][201];
ll d2[201][201];
ll ind[201][201];
ll used[201];
ll eu[50001];
ll ev[50001];
ll ec[50001];
ll ed[50001];
ll mark[50001];
priority_queue<pii(ll),vector<pii(ll)>,greater<pii(ll)>> pq; 
void get(int u, int v)
{
    if (u==v) vec=vec2;
    used[u]=1;
    for (int i=1;i<=n;i++) if ((ind[u][i])and(d1[u][v]==ec[ind[u][i]]+d1[i][v])and(!used[i]))
    {
        vec2.push_back(ind[u][i]);
        get(i,v);
        vec2.pop_back();
    }
}
int main()
{
	fio;
    cin>>n>>m;
    for (i=1;i<=m;i++)
    {
        cin>>eu[i]>>ev[i]>>ec[i]>>ed[i];
    }
    for (i=1;i<=n;i++) for (j=1;j<=n;j++)
    {
        d1[i][j]=1e18;
    }
    for (i=1;i<=n;i++)
    {
        d1[i][i]=0;
    }
    for (i=1;i<=m;i++)
    {
        d1[eu[i]][ev[i]]=min(d1[eu[i]][ev[i]],ec[i]);
        if (d1[eu[i]][ev[i]]==ec[i])
        ind[eu[i]][ev[i]]=i;
    }
    for (k=1;k<=n;k++)
    for (i=1;i<=n;i++)
    for (j=1;j<=n;j++)
    {
        d1[i][j]=min(d1[i][j],d1[i][k]+d1[k][j]);
    }
    res=d1[1][n]+d1[n][1];
    res=min(res,1e18);

    

    u=1,v=n;
    for (i=1;i<=m;i++)
    {
        mark[i]=0;
    }
    for (i=1;i<=n;i++)
    {
        used[i]=0;
    }
    vec2.clear();
    vec.clear();
    if (d1[u][v]<1e18)
    {
    get(u,v);
    for (i=1;i<=vec.size();i++) mark[vec[i-1]]=i;
    // for (auto g : vec) cout<<g<<' '; cout<<endl;

    for (i=1;i<=n;i++) for (j=1;j<=n;j++)
    {
        d2[i][j]=1e18;
    }
    for (i=1;i<=n;i++) d2[i][i]=0;
    for (i=1;i<=m;i++) if (!mark[i])
    {
        d2[eu[i]][ev[i]]=min(d1[eu[i]][ev[i]],ec[i]);
    }
    for (k=1;k<=n;k++)
    for (i=1;i<=n;i++)
    for (j=1;j<=n;j++)
    {
        d2[i][j]=min(d2[i][j],d2[i][k]+d2[k][j]);
    }
    for (i=1;i<=m;i++) if (!mark[i]) 
    {
        ed[i]+=min(d1[u][v],d1[u][ev[i]]+ec[i]+d1[eu[i]][v]);
    }
    else
    {
        a=1e18;
        for (j=1;j<=mark[i];j++) for (k=mark[i];k<=vec.size();k++)
        {
            b=eu[vec[j-1]];
            c=ev[vec[k-1]];
            a=min(a,d1[u][b]+d2[b][c]+d1[c][v]);
        }
        ed[i]+=a;
    }

    }
    else
    {
    for (i=1;i<=m;i++)
    {
        ed[i]+=min(d1[u][v],d1[u][ev[i]]+ec[i]+d1[eu[i]][v]);
    }
    }


    u=n,v=1;
    for (i=1;i<=m;i++)
    {
        mark[i]=0;
    }
    for (i=1;i<=n;i++)
    {
        used[i]=0;
    }
    vec2.clear();
    vec.clear();
    if (d1[u][v]<1e18)
    {
    get(u,v);
    for (i=1;i<=vec.size();i++) mark[vec[i-1]]=i;
    for (i=1;i<=n;i++) for (j=1;j<=n;j++)
    {
        d2[i][j]=1e18;
    }
    for (i=1;i<=n;i++) d2[i][i]=0;
    for (i=1;i<=m;i++) if (!mark[i])
    {
        d2[eu[i]][ev[i]]=min(d1[eu[i]][ev[i]],ec[i]);
    }
    for (k=1;k<=n;k++)
    for (i=1;i<=n;i++)
    for (j=1;j<=n;j++)
    {
        d2[i][j]=min(d2[i][j],d2[i][k]+d2[k][j]);
    }
    for (i=1;i<=m;i++) if (!mark[i]) 
    {
        ed[i]+=min(d1[u][v],d1[u][ev[i]]+ec[i]+d1[eu[i]][v]);
    }
    else
    {
        a=1e18;
        for (j=1;j<=mark[i];j++) for (k=mark[i];k<=vec.size();k++)
        {
            b=eu[vec[j-1]];
            c=ev[vec[k-1]];
            a=min(a,d1[u][b]+d2[b][c]+d1[c][v]);
        }
        ed[i]+=a;
    }
    }
    else
    {
    for (i=1;i<=m;i++)
    {
        ed[i]+=min(d1[u][v],d1[u][ev[i]]+ec[i]+d1[eu[i]][v]);
    }
    }


    for (i=1;i<=m;i++) res=min(res,ed[i]);
    if (res==1e18) cout<<-1 ; else cout<<res;
    cout<<endl;
}
// Normie28;

Compilation message

ho_t4.cpp:23: warning: ignoring '#pragma comment ' [-Wunknown-pragmas]
   23 | #pragma comment(linker, "/stack:200000000")
      | 
ho_t4.cpp: In function 'int main()':
ho_t4.cpp:171:15: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  171 |     for (i=1;i<=vec.size();i++) mark[vec[i-1]]=i;
      |              ~^~~~~~~~~~~~
ho_t4.cpp:196:50: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  196 |         for (j=1;j<=mark[i];j++) for (k=mark[i];k<=vec.size();k++)
      |                                                 ~^~~~~~~~~~~~
ho_t4.cpp:229:15: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  229 |     for (i=1;i<=vec.size();i++) mark[vec[i-1]]=i;
      |              ~^~~~~~~~~~~~
ho_t4.cpp:252:50: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  252 |         for (j=1;j<=mark[i];j++) for (k=mark[i];k<=vec.size();k++)
      |                                                 ~^~~~~~~~~~~~

Subtask #1
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 37 ms 1356 KB Output is correct
2 Correct 10 ms 976 KB Output is correct
3 Correct 29 ms 1280 KB Output is correct
4 Correct 29 ms 1328 KB Output is correct
5 Correct 1 ms 460 KB Output is correct
6 Correct 10 ms 972 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Incorrect 38 ms 1348 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #2
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 51 ms 3144 KB Output is correct
2 Correct 53 ms 3268 KB Output is correct
3 Correct 65 ms 3156 KB Output is correct
4 Correct 29 ms 1288 KB Output is correct
5 Correct 37 ms 1304 KB Output is correct
6 Correct 12 ms 976 KB Output is correct
7 Correct 10 ms 964 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 31 ms 2808 KB Output is correct
10 Correct 32 ms 2876 KB Output is correct
11 Correct 43 ms 3140 KB Output is correct
12 Correct 43 ms 3156 KB Output is correct
13 Correct 49 ms 3180 KB Output is correct
14 Correct 43 ms 3192 KB Output is correct

Subtask #3
21.0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 29 ms 1356 KB Output is correct
2 Correct 21 ms 1284 KB Output is correct
3 Correct 52 ms 3540 KB Output is correct
4 Correct 10 ms 972 KB Output is correct
5 Correct 56 ms 4092 KB Output is correct
6 Correct 1 ms 328 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 30 ms 3728 KB Output is correct
9 Correct 30 ms 3740 KB Output is correct
10 Correct 43 ms 4036 KB Output is correct
11 Correct 42 ms 4048 KB Output is correct
12 Correct 40 ms 4036 KB Output is correct
13 Correct 1 ms 332 KB Output is correct
14 Correct 1 ms 332 KB Output is correct
15 Correct 0 ms 332 KB Output is correct
16 Correct 0 ms 332 KB Output is correct
17 Correct 1 ms 328 KB Output is correct
18 Correct 1 ms 332 KB Output is correct
19 Correct 52 ms 4036 KB Output is correct
20 Correct 42 ms 4260 KB Output is correct
21 Correct 40 ms 4148 KB Output is correct
22 Correct 39 ms 4036 KB Output is correct

Subtask #4
0 / 63.0

# 결과 실행 시간 메모리 Grader output
1 Correct 37 ms 1356 KB Output is correct
2 Correct 10 ms 976 KB Output is correct
3 Correct 29 ms 1280 KB Output is correct
4 Correct 29 ms 1328 KB Output is correct
5 Correct 1 ms 460 KB Output is correct
6 Correct 10 ms 972 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Incorrect 38 ms 1348 KB Output isn't correct
11 Halted 0 ms 0 KB -