oj.uz

Submission #976549

# Submission time Handle Problem Language Result Execution time Memory
976549 2024-05-06T17:19:40 Z Haanhtien Relay Marathon (NOI20_relaymarathon) C++14
17 / 100
 242 ms 49104 KB 
#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define ll long long
const ll N=1e5+10;
const ll M=4e5+10;
ll n,m,k;
ll d[N],flag[N],h[N];
ll mark[N],a[N];
struct edge {
    long long u,v,w;
};
edge c[M];
vector<pair<ll,ll>> g[N];
void Dis(){
    priority_queue<pair<ll,ll>,vector<pair<ll,ll>>,greater<pair<ll,ll>>> pq;
    for(long long i=1;i<=n;i++)
        if(d[i]==0) pq.push({0,i});
    while(!pq.empty()){
        ll val=pq.top().fi,u=pq.top().se; pq.pop();
        if(d[u]!=val) continue; 
        for(auto e:g[u]){
            long long w=e.se,v=e.fi;
            if(d[v]==d[u]+w) flag[v]=1;
            if(d[v]>d[u]+w)
            {
                h[v]=h[u],d[v]=d[u]+w,flag[v]=0;
                pq.push({d[v],v});
            }
        }
    }
}
int main ()
{
    //freopen("cities.inp","r",stdin);
    //freopen("cities.out","w",stdout); 
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cin>>n>>m>>k;
    fill(d+1,d+n+1,1e18);
    for(ll i=1;i<=m;i++)
    {
        ll u,v,w;
        cin>>u>>v>>w;
        c[i].u=u;
        c[i].v=v;
        c[i].w=w;
        g[u].push_back({v,w});
        g[v].push_back({u,w});
    }
    for(long long i=1;i<=k;i++)
    {
        long long x;
        cin>>x;
        d[x]=flag[x]=0;
        h[x]=x;
    }
    Dis();
    long long a_main=0,b_main=0,t=1e18;
    for(long long i=1;i<=m;i++)
    {
        long long u=c[i].u,v=c[i].v,w=c[i].w;
        if(d[u]<1e18 && d[v]<1e18)
        {
            if(flag[u]==1 || flag[v]==1 || h[u]!=h[v])
            {
                long long t_try=d[u]+d[v]+w;
                if(t_try<t)
                {
                    a_main=h[u];
                    b_main=h[v];
                    t=t_try;
                }
            }
        }
    }
    //cout<<t<<'\n';
    long long t2=1e18,abest1=1e18,abest2=1e18,bbest1=1e18,bbest2=1e18,a1=1e18,b1=1e18;
    for(long long i=1;i<=m;i++)
    {
        long long u=c[i].u,v=c[i].v,w=c[i].w;
        if(d[u]<1e18 && d[v]<1e18)
        {
            if(flag[u]==1 || flag[v]==1 || h[u]!=h[v])
            {
                long long t_try=d[u]+d[v]+w;
                //cout<<u<<" "<<v<<" "<<h[u]<<" w "<<h[v]<<'\n';
                if(h[u]!=a_main && h[v]!=a_main && h[u]!=b_main && h[v]!=b_main && t_try<t2)
                {
                    t2=t_try;
                    continue;
                }
                if((h[u]==a_main && h[v]!=b_main) || (h[v]==a_main && h[u]!=b_main))
                {
                    if(t_try<abest1)
                    {
                        abest2=abest1;
                        abest1=t_try;
                        a1=(h[u]==a_main ? h[v]:h[u]);
                    }
                    else if(t_try<abest2)
                        abest2=t_try;
                }
                if((h[u]!=a_main && h[v]==b_main) || (h[v]!=a_main && h[u]==b_main))
                {
                    if(t_try<bbest1)
                    {
                        bbest2=bbest1;
                        bbest1=t_try;
                        b1=(h[u]==b_main ? h[v]:h[u]);
                    }
                    else if(t_try<bbest2) bbest2=t_try;
                }
            }
        }
    }
    long long dmin=t+t2;
    //cout<<t2<<'\n';
    if(a1==b1) dmin=min({dmin,abest1+bbest2,abest2+bbest1});
    else dmin=min(dmin,abest1+bbest1);
    cout<<dmin;
    return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6748 KB Output is correct
2 Correct 2 ms 6748 KB Output is correct
3 Correct 1 ms 6764 KB Output is correct
4 Correct 1 ms 6748 KB Output is correct
5 Correct 2 ms 6748 KB Output is correct
6 Correct 4 ms 6748 KB Output is correct
7 Correct 2 ms 6748 KB Output is correct
8 Correct 2 ms 6748 KB Output is correct
9 Correct 2 ms 6748 KB Output is correct
10 Correct 1 ms 6744 KB Output is correct
11 Correct 1 ms 6748 KB Output is correct
12 Correct 1 ms 6748 KB Output is correct
13 Correct 1 ms 6748 KB Output is correct
14 Correct 2 ms 6748 KB Output is correct
15 Correct 1 ms 6748 KB Output is correct
16 Correct 1 ms 6748 KB Output is correct
17 Correct 1 ms 6748 KB Output is correct
18 Correct 2 ms 6748 KB Output is correct
19 Correct 3 ms 6748 KB Output is correct
20 Correct 2 ms 6748 KB Output is correct
21 Correct 1 ms 6748 KB Output is correct
22 Correct 2 ms 6748 KB Output is correct
23 Correct 2 ms 6748 KB Output is correct
24 Correct 2 ms 6748 KB Output is correct
25 Correct 1 ms 6748 KB Output is correct
26 Correct 1 ms 6748 KB Output is correct
27 Correct 1 ms 6748 KB Output is correct
28 Correct 2 ms 6748 KB Output is correct
29 Correct 1 ms 6744 KB Output is correct
30 Correct 2 ms 6748 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6748 KB Output is correct
2 Correct 2 ms 6748 KB Output is correct
3 Correct 1 ms 6764 KB Output is correct
4 Correct 1 ms 6748 KB Output is correct
5 Correct 2 ms 6748 KB Output is correct
6 Correct 4 ms 6748 KB Output is correct
7 Correct 2 ms 6748 KB Output is correct
8 Correct 2 ms 6748 KB Output is correct
9 Correct 2 ms 6748 KB Output is correct
10 Correct 1 ms 6744 KB Output is correct
11 Correct 1 ms 6748 KB Output is correct
12 Correct 1 ms 6748 KB Output is correct
13 Correct 1 ms 6748 KB Output is correct
14 Correct 2 ms 6748 KB Output is correct
15 Correct 1 ms 6748 KB Output is correct
16 Correct 1 ms 6748 KB Output is correct
17 Correct 1 ms 6748 KB Output is correct
18 Correct 2 ms 6748 KB Output is correct
19 Correct 3 ms 6748 KB Output is correct
20 Correct 2 ms 6748 KB Output is correct
21 Correct 1 ms 6748 KB Output is correct
22 Correct 2 ms 6748 KB Output is correct
23 Correct 2 ms 6748 KB Output is correct
24 Correct 2 ms 6748 KB Output is correct
25 Correct 1 ms 6748 KB Output is correct
26 Correct 1 ms 6748 KB Output is correct
27 Correct 1 ms 6748 KB Output is correct
28 Correct 2 ms 6748 KB Output is correct
29 Correct 1 ms 6744 KB Output is correct
30 Correct 2 ms 6748 KB Output is correct
31 Correct 1 ms 6748 KB Output is correct
32 Correct 2 ms 6748 KB Output is correct
33 Correct 1 ms 6748 KB Output is correct
34 Correct 1 ms 6748 KB Output is correct
35 Correct 1 ms 6748 KB Output is correct
36 Correct 2 ms 7004 KB Output is correct
37 Correct 2 ms 7004 KB Output is correct
38 Correct 2 ms 6748 KB Output is correct
39 Correct 18 ms 13404 KB Output is correct
40 Correct 5 ms 7768 KB Output is correct
41 Correct 1 ms 6748 KB Output is correct
42 Correct 5 ms 7772 KB Output is correct
43 Correct 2 ms 6748 KB Output is correct
44 Correct 2 ms 6748 KB Output is correct
45 Correct 1 ms 6748 KB Output is correct
46 Correct 20 ms 13408 KB Output is correct
47 Correct 4 ms 7260 KB Output is correct
48 Correct 17 ms 11356 KB Output is correct
49 Correct 19 ms 13148 KB Output is correct
50 Correct 2 ms 6748 KB Output is correct
51 Correct 2 ms 6748 KB Output is correct
52 Correct 2 ms 6944 KB Output is correct
53 Correct 10 ms 8976 KB Output is correct
54 Correct 18 ms 13404 KB Output is correct
55 Correct 2 ms 6744 KB Output is correct
56 Correct 2 ms 6748 KB Output is correct
57 Correct 1 ms 6748 KB Output is correct
58 Correct 22 ms 13148 KB Output is correct
59 Correct 2 ms 6804 KB Output is correct
60 Correct 2 ms 6748 KB Output is correct

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 11748 KB Output is correct
2 Correct 4 ms 8028 KB Output is correct
3 Incorrect 242 ms 49104 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 58.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6748 KB Output is correct
2 Correct 2 ms 6748 KB Output is correct
3 Correct 1 ms 6764 KB Output is correct
4 Correct 1 ms 6748 KB Output is correct
5 Correct 2 ms 6748 KB Output is correct
6 Correct 4 ms 6748 KB Output is correct
7 Correct 2 ms 6748 KB Output is correct
8 Correct 2 ms 6748 KB Output is correct
9 Correct 2 ms 6748 KB Output is correct
10 Correct 1 ms 6744 KB Output is correct
11 Correct 1 ms 6748 KB Output is correct
12 Correct 1 ms 6748 KB Output is correct
13 Correct 1 ms 6748 KB Output is correct
14 Correct 2 ms 6748 KB Output is correct
15 Correct 1 ms 6748 KB Output is correct
16 Correct 1 ms 6748 KB Output is correct
17 Correct 1 ms 6748 KB Output is correct
18 Correct 2 ms 6748 KB Output is correct
19 Correct 3 ms 6748 KB Output is correct
20 Correct 2 ms 6748 KB Output is correct
21 Correct 1 ms 6748 KB Output is correct
22 Correct 2 ms 6748 KB Output is correct
23 Correct 2 ms 6748 KB Output is correct
24 Correct 2 ms 6748 KB Output is correct
25 Correct 1 ms 6748 KB Output is correct
26 Correct 1 ms 6748 KB Output is correct
27 Correct 1 ms 6748 KB Output is correct
28 Correct 2 ms 6748 KB Output is correct
29 Correct 1 ms 6744 KB Output is correct
30 Correct 2 ms 6748 KB Output is correct
31 Correct 1 ms 6748 KB Output is correct
32 Correct 2 ms 6748 KB Output is correct
33 Correct 1 ms 6748 KB Output is correct
34 Correct 1 ms 6748 KB Output is correct
35 Correct 1 ms 6748 KB Output is correct
36 Correct 2 ms 7004 KB Output is correct
37 Correct 2 ms 7004 KB Output is correct
38 Correct 2 ms 6748 KB Output is correct
39 Correct 18 ms 13404 KB Output is correct
40 Correct 5 ms 7768 KB Output is correct
41 Correct 1 ms 6748 KB Output is correct
42 Correct 5 ms 7772 KB Output is correct
43 Correct 2 ms 6748 KB Output is correct
44 Correct 2 ms 6748 KB Output is correct
45 Correct 1 ms 6748 KB Output is correct
46 Correct 20 ms 13408 KB Output is correct
47 Correct 4 ms 7260 KB Output is correct
48 Correct 17 ms 11356 KB Output is correct
49 Correct 19 ms 13148 KB Output is correct
50 Correct 2 ms 6748 KB Output is correct
51 Correct 2 ms 6748 KB Output is correct
52 Correct 2 ms 6944 KB Output is correct
53 Correct 10 ms 8976 KB Output is correct
54 Correct 18 ms 13404 KB Output is correct
55 Correct 2 ms 6744 KB Output is correct
56 Correct 2 ms 6748 KB Output is correct
57 Correct 1 ms 6748 KB Output is correct
58 Correct 22 ms 13148 KB Output is correct
59 Correct 2 ms 6804 KB Output is correct
60 Correct 2 ms 6748 KB Output is correct
61 Correct 33 ms 11748 KB Output is correct
62 Correct 4 ms 8028 KB Output is correct
63 Incorrect 242 ms 49104 KB Output isn't correct
64 Halted 0 ms 0 KB -