oj.uz

답안 #995217

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
995217 2024-06-08T16:11:36 Z modwwe Olympic Bus (JOI20_ho_t4) C++17
11 / 100
 89 ms 3772 KB 
#pragma GCC optimize("Ofast,unroll-loops")
#include<bits/stdc++.h>
//#define int long long
//#define ll long long
#define down cout<<'\n';
#define NHP     ios_base::sync_with_stdio(0);cout.tie(0);cin.tie(0);
#define modwwe  int t;cin>>t; while(t--)
#define bit(i,j) (i>>j&1)
#define sobit(a) __builtin_popcountll(a)
#define task "test"
#define fin(x) freopen(x".inp","r",stdin)
#define fou(x) freopen(x".ans","w",stdout)
#define pb push_back
#define checktime   cerr << (double)clock() / CLOCKS_PER_SEC * 1000  << " ms";
using namespace std;
const int inf=1e9;

void phongbeo();
const int mod2=1e9+7;
const int  mod1=998244353;
struct icd
{
    int a,b;
};
struct ib
{
    int a;
    int b;
};
struct ic
{
    int a,b,c;
};
struct id
{
    int a,b,c,d;
};
struct ie
{
    int a,b,c, d,e,f;

};
int n,m,s1,s2,s4,s3,sf,k,r,mid,s5,s6,mx,s7,s8,s9,mx2,res,dem2=0,dem=0,l;
int  i,s10,s12;
int el=29;
main()
{
#ifndef ONLINE_JUDGE
    //fin(task),fou(task);
#endif
    NHP
    /// cin>>s1;
    // modwwe
    phongbeo(),down
}
struct cmp
{
    bool operator()(ic a,ic b)
    {
        return a.a>b.a;
    }
};
int color[201];
vector<ic> v[201];
int dp[201][201];
id a[50001];
bool b[50001];

int diditcha(int c,int y)
{
    priority_queue<ic,vector<ic>,cmp>p;
    p.push({0,c,0});
    memset(color,-1,sizeof color);
    while(!p.empty())
    {
        ic x=p.top();
        p.pop();
        if(color[x.b]!=-1) continue;
        color[x.b]=x.c;
        if(x.b==y) return x.a;
        for(auto f:v[x.b])
            p.push({x.a+f.b,f.a,f.c});
    }
    return inf;
}
void del(int x,int y)
{
    for(int i=0; i<v[x].size(); i++)
        if(v[x][i].c==y)
        {
            v[x].erase(v[x].begin()+i);
            return;
        }
}
void add(int x,int y,int s2,int c)
{
    v[x].pb({y,s2,c});
}
void phongbeo()
{
    cin>>n;
    for(int i=1; i<=n; i++)
    {
        for(int j=1; j<=n; j++)
            dp[i][j]=inf;
        dp[i][i]=0;
    }
    cin>>m;
    for(int j=1; j<=m; j++)
    {
        cin>>l>>r>>s2>>s3;
        a[j]= {l,r,s2,s3};
        v[l].pb({r,s2,j});
        dp[l][r]=min(dp[l][r],s2);
    }
    for(int k=1; k<=n; k++)
        for(int i=1; i<=n; i++)
            for(int j=1; j<=n; j++)
                dp[i][j]=min(dp[i][j],dp[i][k]+dp[k][j]);
            s4+=diditcha(1,n);
    s2=n;
    while(color[s2]!=-1)
    {        b[color[s2]]=1,s2=a[color[s2]].a;
    }
    s5+= diditcha(n,1);
    s3=s4+s5;
    s2=1;
    if(s3>=inf) s3=2*inf;
    while(color[s2]!=-1)
    {
        b[color[s2]]=1,s2=a[color[s2]].a;
    }
    for(int j=1; j<=m; j++)
        if(b[j])
        {
            del(a[j].a,j),add(a[j].b,a[j].a,a[j].c,j);
            s5=diditcha(1,n);
            s4=diditcha(n,1);
            s3=min({s4+s5+a[j].d,s3});
            del(a[j].b,j),add(a[j].a,a[j].b,a[j].c,j);
        }
        else{
                 if(min(dp[1][a[j].b]+dp[a[j].a][n]+a[j].c,dp[1][n])<inf&&min(dp[n][a[j].b]+dp[a[j].a][1]+a[j].c,dp[n][1])+a[j].d<inf)
        s3=min(s3,min(dp[1][a[j].b]+dp[a[j].a][n]+a[j].c,dp[1][n])+min(dp[n][a[j].b]+dp[a[j].a][1]+a[j].c,dp[n][1])+a[j].d);}
 if(s3>=2*inf)cout<<-1;
 else cout<<s3;
}

Compilation message

ho_t4.cpp:46:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   46 | main()
      | ^~~~
ho_t4.cpp: In function 'void del(int, int)':
ho_t4.cpp:88:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<ic>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   88 |     for(int i=0; i<v[x].size(); i++)
      |                  ~^~~~~~~~~~~~
ho_t4.cpp: In function 'void phongbeo()':
ho_t4.cpp:117:9: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
  117 |         for(int i=1; i<=n; i++)
      |         ^~~
ho_t4.cpp:120:13: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
  120 |             s4+=diditcha(1,n);
      |             ^~

Subtask #1
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 600 KB Output is correct
2 Correct 6 ms 640 KB Output is correct
3 Correct 6 ms 604 KB Output is correct
4 Correct 7 ms 668 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 6 ms 604 KB Output is correct
7 Incorrect 0 ms 348 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 28 ms 3756 KB Output is correct
2 Correct 33 ms 3684 KB Output is correct
3 Correct 23 ms 3140 KB Output is correct
4 Correct 6 ms 600 KB Output is correct
5 Correct 6 ms 604 KB Output is correct
6 Correct 6 ms 648 KB Output is correct
7 Correct 6 ms 604 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 20 ms 2976 KB Output is correct
10 Correct 25 ms 2664 KB Output is correct
11 Correct 89 ms 3160 KB Output is correct
12 Correct 46 ms 3132 KB Output is correct
13 Correct 52 ms 3644 KB Output is correct
14 Correct 59 ms 3772 KB Output is correct

Subtask #3
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 600 KB Output is correct
2 Incorrect 6 ms 604 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 63.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 600 KB Output is correct
2 Correct 6 ms 640 KB Output is correct
3 Correct 6 ms 604 KB Output is correct
4 Correct 7 ms 668 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 6 ms 604 KB Output is correct
7 Incorrect 0 ms 348 KB Output isn't correct
8 Halted 0 ms 0 KB -