Submission #1275479

#	Time	Username	Problem	Language	Result	Execution time	Memory
1275479		zagaro	Dreaming (IOI13_dreaming)	C++20	100 / 100	55 ms	16828 KiB

dreaming

#include<bits/stdc++.h>
#include "dreaming.h"
#include<ext/pb_ds/assoc_container.hpp>
/**zagaro & lauren <3**/
#define mod 1000000007 //1e9 + 7
#define pi acos(-1)
#define wl while
#define str string
#define ENDL "\n"
#define sal ' '
#define tp_set ll
#define prc(n) cout.precision(n);cout<<fixed;
#define ord_set tree<tp_set, null_type, less<tp_set>, rb_tree_tag, tree_order_statistics_node_update>
typedef long long ll;
typedef bool bl;
typedef char car;
using namespace std;
using namespace __gnu_pbds;
ll n, m, l;
vector<vector<pair<ll,ll> > > adj;
vector<bl> vis;
vector<pair<ll,ll> > may;
void dfs(ll nod, ll par){
    vis[nod] = true;
    for(int i=0;i<adj[nod].size();i++){
        if(adj[nod][i].first != par){
            dfs(adj[nod][i].first, nod);
            if(may[adj[nod][i].first].first + adj[nod][i].second > may[nod].first){
                may[nod].second = may[nod].first;
                may[nod].first = may[adj[nod][i].first].first + adj[nod][i].second;
            }
            else if(may[adj[nod][i].first].first + adj[nod][i].second > may[nod].second){
                may[nod].second = may[adj[nod][i].first].first + adj[nod][i].second;
            }
        }
    }
    return ;
}
int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
    ll nod, par, a, val, r=0, w=0, t, q;
    n=N;m=M;l=L;
    q = n-1-m;
    adj.assign(n, vector<pair<ll,ll> > (0, {0, 0}));
    vis.assign(n, false);
    may.assign(n, {0,0});
    for(int i=0;i<M;i++){
        adj[A[i]].push_back({B[i], T[i]});
        adj[B[i]].push_back({A[i], T[i]});
    }
    queue<tuple<ll,ll,ll> > pq;
    vector<ll> vec;
    for(int i=0;i<n;i++){
        if(!vis[i]){
            dfs(i, -1);
            r = may[i].first;
            w = max(w, may[i].first);
            for(int j=0;j<adj[i].size();j++)pq.push({adj[i][j].first, i, adj[i][j].second});
            wl(!pq.empty()){
                tie(nod, par, val) = pq.front();
                pq.pop();
                if(may[par].first == may[nod].first+val)a=may[par].second;
                else a=may[par].first;
                a += val;
                if(a > may[nod].first){
                    may[nod].second = may[nod].first;
                    may[nod].first = a;
                }
                else if(a > may[nod].second)may[nod].second = a;
                w = max(w, may[nod].first);
                r = min(r, may[nod].first);
                for(int j=0;j<adj[nod].size();j++){
                    if(adj[nod][j].first != par){
                        pq.push({adj[nod][j].first, nod, adj[nod][j].second});
                    }
                }
            }
            vec.push_back(r);
        }
    }
    t = vec.size()-1;
    sort(vec.begin(), vec.end());
    if(q == 0){}
    else if(q == 1)w = max(w, vec[t] + vec[t-1] + l);
    else w = max(w ,max(vec[t] + vec[t-1] + l, vec[t-1]+vec[t-2]+2*l));
    return w;
}

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