Submission #1313714

#	Time	Username	Problem	Language	Result	Execution time	Memory
1313714		husseinjuanda	Dreaming (IOI13_dreaming)	C++20	47 / 100	44 ms	17344 KiB

dreaming

#include "dreaming.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long

vector<int> dp;
vector<vector<pair<int, int>>> g;
vector<int> d;
vector<int> h;

void dfs(int k, int p){
    d[k] = 1;
    for(int y = 0; y < g[k].size(); y++){
        if(g[k][y].first == p) continue;
        dfs(g[k][y].first, k);
        dp[k] = max(dp[k], dp[g[k][y].first]+g[k][y].second);
    }
}

int m = 2e9;
int mmx = 0;

void reroot(int k, int p, int up){
    int mx = 0;
    int mx1 = 0;
    for(int y = 0; y < g[k].size(); y++){
        if(g[k][y].first == p) continue;
        if(mx < dp[g[k][y].first] + g[k][y].second){
            mx1 = mx;
            mx = dp[g[k][y].first] + g[k][y].second;
        }else{
            mx1 = max(mx1, dp[g[k][y].first] + g[k][y].second);
        }
    }
    h[k] = max(dp[k], up);
    for(int y = 0; y < g[k].size(); y++){
        if(g[k][y].first == p) continue;
        if(mx == dp[g[k][y].first]+g[k][y].second){
            reroot(g[k][y].first, k, max(mx1, up)+g[k][y].second);
        }else{
            reroot(g[k][y].first, k, max(mx, up)+g[k][y].second);
        }
    }
    mmx = max(mmx, h[k]);
    m = min(m, h[k]);
}

int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
    g.resize(N+1);
    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]});
    }
    int mn = 0;
    d.resize(N);
    h.resize(N);
    dp.resize(N);
    multiset<int> s;
    for(int i = 0; i < N; i++){
        if(d[i] == 1) continue;
        m = 1e9;
        dfs(i, -1);
        reroot(i, -1, 0);
        d[i] = -m;
        // cout << m << "\n";
        s.insert(m+L);
    }
    for(int i = 0; i < N; i++){
        if(d[i] == 1) continue;
        s.erase(s.find(-d[i]+L));
        if(s.size() >= 2){
            auto it = s.rbegin();
            auto it1 = it;
            it1++;
            mn = max(*it + *it1, *it - d[i]);
        }else if(s.size() >= 1){
            mn =  -d[i] + *s.rbegin();
        }
        s.insert(-d[i]+L);
    }
    // cout << mn << " " << mmx << endl;
    return max(mn, mmx);
}

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