Submission #1276592

#	Time	Username	Problem	Language	Result	Execution time	Memory
1276592		avohado	Dreaming (IOI13_dreaming)	C++20	0 / 100	97 ms	131072 KiB

dreaming

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

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