Submission #1278418

#	Time	Username	Problem	Language	Result	Execution time	Memory
1278418		avohado	Dreaming (IOI13_dreaming)	C++20	100 / 100	96 ms	16648 KiB

dreaming

#include <bits/stdc++.h>
#include "dreaming.h"
using namespace std;
#define mod 1000000007
#define maxn 100005
#define f first
#define s second
#define ll long long
#define pb(x) push_back(x)
#define mp make_pair
vector<pair<int, ll>> g[maxn];
bool a[maxn];
pair<int, ll> b[maxn][2];
int c[maxn];
queue<pair<int, ll>>q;
ll dfs(int u, int p){
    long long mn=INT64_MAX;
    for(auto i:g[u]){
        if(i.f!=p){
            if(b[u][0].f!=i.f){
                if(b[u][0].s+i.s>b[i.f][0].s){
                    b[i.f][1]=b[i.f][0];
                    b[i.f][0]=mp(u,b[u][0].s+i.s);
                }else if(b[u][0].s+i.s>b[i.f][1].s){
                    b[i.f][1]=mp(u,b[u][0].s+i.s);
                }
            }else if(b[u][1].s+i.s>b[i.f][0].s){
                b[i.f][1]=b[i.f][0];
                b[i.f][0]=mp(u,b[u][1].s+i.s);
            }else if(b[u][1].s+i.s>b[i.f][1].s){
                b[i.f][1]=mp(u,b[u][1].s+i.s);
            }
            mn=min(mn, dfs(i.f, u));
        }
    }
    return min(mn, b[u][0].s);
}
int travelTime(int N,int M,int L,int *A,int *B,int *T){
    for(int i=0; i<M; i++){
        g[A[i]].pb(mp(B[i], T[i]));
        g[B[i]].pb(mp(A[i], T[i]));
    }
    vector<ll> v;
    for(int i=0; i<N; i++){
        if(g[i].size()==0){
            v.pb(0);
        }else if(g[i].size()==1){
            q.push(mp(i, 0));
        }
        b[i][0].f=b[i][1].f=i;
        b[i][1].s=-10000;
        c[i]=g[i].size();
    }
    while(q.size()){
        int u=q.front().f;q.pop();
        a[u]=1;
        if(c[u]==0){
            v.pb(dfs(u, u));
            continue;
        }
        for(auto i:g[u]){
            if(!a[i.f]){
                if(b[u][0].s+i.s>b[i.f][0].s){
                    b[i.f][1]=b[i.f][0];
                    b[i.f][0]=mp(u,b[u][0].s+i.s);
                }else{
                    b[i.f][1]=mp(u,b[u][0].s+i.s);
                }
                c[i.f]--;
                if(c[i.f]==1){
                    q.push(mp(i.f, b[i.f][0].s));
                }
            }
        }
    }
    sort(v.begin(), v.end(), greater<>());
    long long ans=0;
    if(v.size()==1){
        ans= v[0];
    }else if(v.size()==2){
        ans= v[0]+L+v[1]; 
    }else{
        ans= max(v[0]+L+v[1], v[1]+v[2]+L*2);
    }
    for(int i=0; i<N; i++){
        if(g[i].size()==1){
            ans=max(ans, b[i][0].s);
        }
    }
    return ans;
}
/*int main(){
    int n,m,k;
    cin >> n >> m >> k;
    int a[m], B[m],c[m];
    for(int i=0; i<n; i++)
    cin >> a[i] >> B[i] >> c[i];
    cout << travelTime(n,m,k,a,B,c)<<"\n";
}*/

• Subtask 1: 14 / 14
• Subtask 2: 10 / 10
• Subtask 3: 23 / 23
• Subtask 4: 18 / 18
• Subtask 5: 12 / 12
• Subtask 6: 23 / 23