oj.uz

Submission #952853

# Submission time Handle Problem Language Result Execution time Memory
952853 2024-03-25T03:07:34 Z sondos225 Relay Marathon (NOI20_relaymarathon) C++17
25 / 100
 3659 ms 242236 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)
            {
                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 23 ms 8284 KB Output is correct
2 Correct 4 ms 4188 KB Output is correct
3 Correct 3659 ms 236128 KB Output is correct
4 Correct 988 ms 86968 KB Output is correct
5 Correct 152 ms 20108 KB Output is correct
6 Correct 49 ms 12376 KB Output is correct
7 Correct 186 ms 24960 KB Output is correct
8 Correct 26 ms 8540 KB Output is correct
9 Correct 42 ms 11464 KB Output is correct
10 Correct 30 ms 9300 KB Output is correct
11 Correct 3360 ms 242236 KB Output is correct
12 Correct 36 ms 10332 KB Output is correct
13 Correct 892 ms 65908 KB Output is correct
14 Correct 87 ms 17100 KB Output is correct
15 Correct 3062 ms 239520 KB Output is correct
16 Correct 41 ms 9044 KB Output is correct
17 Correct 880 ms 125044 KB Output is correct
18 Correct 4 ms 4188 KB Output is correct
19 Correct 1301 ms 170532 KB Output is correct
20 Correct 95 ms 16116 KB Output is correct
21 Correct 55 ms 13844 KB Output is correct
22 Correct 29 ms 9308 KB Output is correct
23 Correct 16 ms 6492 KB Output is correct
24 Correct 2959 ms 200180 KB Output is correct
25 Correct 46 ms 10064 KB Output is correct
26 Correct 31 ms 7760 KB Output is correct
27 Correct 33 ms 8820 KB Output is correct
28 Correct 9 ms 4952 KB Output is correct
29 Correct 70 ms 13392 KB Output is correct
30 Correct 184 ms 27340 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 -