oj.uz

Submission #952856

# Submission time Handle Problem Language Result Execution time Memory
952856 2024-03-25T03:11:52 Z sondos225 Relay Marathon (NOI20_relaymarathon) C++17
25 / 100
 3639 ms 241624 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;
template<typename T>using ordered_set = tree<T,null_type,less_equal<T>,rb_tree_tag,tree_order_statistics_node_update>;//find_by_order(ind);
//order_of_key()
#define int long long
#define fast ios_base::sync_with_stdio(0);cin.tie(NULL);cout.tie(NULL);
#define pb push_back
#define yes "YES"
#define no "NO"
#define bigg INT_MAX
#define debug(x) cout<<(#x)<<" = " <<x<<endl;
#define all(x) x.begin(),x.end()
#define sz size()
#define nn '\n'
#define mms(x,y) memset(x,y,sizeof(x))
#define forr(i,j,n) for (int i=j; i<n; i++)
#define forn(i,j,n) for (int i=j; i>n; i--)
#define fi first
#define se second
#define la "LA"
#define cinn(x,y) for(int i=0; i<y; i++) cin>>x[i];
#define pii pair<int,int>
int par[100005]={ };
int fin(int x)
{
    if (x==par[x]) return x;
    return par[x]=fin(x);
}
signed main()
{
//    #ifndef LOCAL
//    freopen("lifeguards.in","r",stdin);
//    freopen("lifeguards.out","w", stdout);
//    #endif
    fast
    int n,m,k;
    cin>>n >>m >>k;
//    int dis[n+1][n+1];
//    forr(i,1,n+1)
//    {
//        forr(j,1,n+1)
//        {
//            if (i==j) dis[i][j]=0;
//            else dis[i][j]=bigg;
//        }
//    }
vector<pii> a[n+1];
    forr(i,0,m)
    {
        int x,y,z;
        cin>>x >>y >>z;
        a[x].pb({y,z});
        a[y].pb({x,z});
//        dis[x][y]=z;
//        dis[y][x]=z;
    }
    int s[k];
    priority_queue<array<int,3>> q;
    bool b[n+1]= { };

  //  int last[n+1]={ };
    forr(i,0,k)
    {
        cin>>s[i];
        //if (s[i]==1 || s[i]==2) continue;
        q.push({0,s[i],s[i]});
        b[s[i]]=1;
        par[s[i]]=s[i];
       // last[s[i]]=s[i];
    }
    set <pii>vis;
    int ans1=0;
    int a1=0, a2=0;
    while(!q.empty())
    {
        int c=q.top()[0], x=q.top()[1], last=q.top()[2];
        q.pop();
        if (vis.find({x,fin(last)})!=vis.end()) continue;
        par[x]=fin(last);
      //  cout<<c<<' '<<x<<endl;
        if (b[x] && c!=0)
        {
        //    cout<<x<<' '<<c<<endl;
            ans1=-c;
            a1=x;
            a2=par[x];
            break;
        }
       // if (!b[x])
       vis.insert({x,par[x]});
//       cout<<"PUT"<<x<<' '<<last<<endl;
        for(auto y:a[x])
        {
//            cout"DWAR"<<y.fi<<' '<<par[x]<<endl;
            if (vis.find({y.fi,par[x]})==vis.end() && par[x]!=y.fi)
            {
                int o=abs(c);
                o+=y.se;
                q.push({-o,y.fi,par[x]});

           //     cout<<yes<<y.fi<<' '<<y.se<<' '<<last<<endl;
            }
        }
    }
    while(!q.empty()) q.pop();
   // q.clear();
    vis.clear();
    mms(par,0);
    forr(i,0,k)
    {
        //cin>>s[i];
        if (s[i]==a1 || s[i]==a2) continue;
        q.push({0,s[i],s[i]});
      //  b[s[i]]=1;
        par[s[i]]=s[i];
       // last[s[i]]=s[i];
    }
    ///////////////
    while(!q.empty())
    {
        int c=q.top()[0], x=q.top()[1], last=q.top()[2];
        q.pop();
        if (vis.find({x,fin(last)})!=vis.end()) continue;
        par[x]=fin(last);
      //  cout<<c<<' '<<x<<endl;
        if (b[x] && c!=0)
        {
        //    cout<<x<<' '<<c<<endl;
            ans1+=(-c);
           // a1=x;
           // a2=par[x];
            break;
        }
       // if (!b[x])
       vis.insert({x,par[x]});
//       cout<<"PUT"<<x<<' '<<last<<endl;
        for(auto y:a[x])
        {
//            cout"DWAR"<<y.fi<<' '<<par[x]<<endl;
            if (vis.find({y.fi,par[x]})==vis.end() && par[x]!=y.fi && y.fi!=a1 && y.fi!=a2)
            {
                int o=abs(c);
                o+=y.se;
                q.push({-o,y.fi,par[x]});

           //     cout<<yes<<y.fi<<' '<<y.se<<' '<<last<<endl;
            }
        }
    }
    /////////////////
    cout<<ans1;
//    vector<pii> top3[n+1];
//    forr(q,1,n+1)
//    {
//        //vector<pii> cur;
//        forr(i,1,n+1)
//        {
//
//            forr(j,1,n+1)
//            {
//                if (i==j) continue;
//                dis[i][j]=min(dis[i][j],dis[i][q]+dis[q][j]);
//            }
//            //cout<<la<<i<<' '<<j<<' '<<dis[i][j]<<endl;
//                    }
////if (b[i] && b[j]) cur.pb({dis[i][j],j});
////        sort(all(cur));
////        if(cur.sz>0) top3[i].pb(cur[0]);
////        if(cur.sz>1) top3[i].pb(cur[1]);
////        if(cur.sz>2) top3[i].pb(cur[2]);
//    }
//     forr(i,1,n+1)
//    {
//        vector<pii> cur;
//        forr(j,1,n+1)
//        {
//            if (i==j) continue;
//            if (b[i] && b[j]) cur.pb({dis[i][j],j});//cout<<la<<i<<' '<<j<<' '<<dis[i][j]<<endl;
//        }
//        sort(all(cur));
//        if(cur.sz>0) top3[i].pb(cur[0]);
//        if(cur.sz>1) top3[i].pb(cur[1]);
//        if(cur.sz>2) top3[i].pb(cur[2]);
//    }
//    int ans=bigg;
//    forr(i,0,k)
//    {
//        int x=s[i];
//        if (top3[x].sz==0) continue;
//        forr(j,0,k)
//        {
//            if (i==j) continue;
//            int y=s[j];
//            int cur=top3[x][0].fi;
//            int nope=top3[x][0].se;
//            if (y==nope) continue;
//            if (top3[y].sz==0) continue;
//            if (top3[y][0].se!=nope && top3[y][0].se!=x) cur+=top3[y][0].fi;
//            else if (top3[y].sz==1) continue;
//            else if (top3[y][1].se!=nope && top3[y][1].se!=x) cur+=top3[y][1].fi;
//            else if (top3[y].sz==2) continue;
//            else if (top3[y][2].se!=nope && top3[y][2].se!=x) cur+=top3[y][2].fi;
//            else if (top3[y].sz==3) continue;
//            else cur+=top3[y][3].fi;
//          //  cout<<x<<' '<<y<<' '<<cur<<endl;
//            ans=min(ans,cur);
//        }
//    }
//    if (ans==bigg) ans/=0;
//    cout<<ans;
    return 0;
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 1116 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 1116 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 8536 KB Output is correct
2 Correct 4 ms 4188 KB Output is correct
3 Correct 3639 ms 237452 KB Output is correct
4 Correct 1024 ms 88828 KB Output is correct
5 Correct 171 ms 20380 KB Output is correct
6 Correct 49 ms 12368 KB Output is correct
7 Correct 188 ms 25340 KB Output is correct
8 Correct 32 ms 8620 KB Output is correct
9 Correct 48 ms 11568 KB Output is correct
10 Correct 32 ms 9556 KB Output is correct
11 Correct 3324 ms 241624 KB Output is correct
12 Correct 37 ms 10764 KB Output is correct
13 Correct 933 ms 66120 KB Output is correct
14 Correct 85 ms 17356 KB Output is correct
15 Correct 3214 ms 238112 KB Output is correct
16 Correct 37 ms 9084 KB Output is correct
17 Correct 888 ms 126420 KB Output is correct
18 Correct 6 ms 4184 KB Output is correct
19 Correct 1294 ms 170908 KB Output is correct
20 Correct 90 ms 16528 KB Output is correct
21 Correct 58 ms 14164 KB Output is correct
22 Correct 33 ms 9300 KB Output is correct
23 Correct 18 ms 6648 KB Output is correct
24 Correct 3058 ms 214244 KB Output is correct
25 Correct 49 ms 11344 KB Output is correct
26 Correct 30 ms 8692 KB Output is correct
27 Correct 33 ms 9808 KB Output is correct
28 Correct 9 ms 5208 KB Output is correct
29 Correct 71 ms 15288 KB Output is correct
30 Correct 164 ms 30928 KB Output is correct

Subtask #4
0 / 58.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 1116 KB Output isn't correct
2 Halted 0 ms 0 KB -