Submission #1178826

#	Time	Username	Problem	Language	Result	Execution time	Memory
1178826		aguss	Dreaming (IOI13_dreaming)	C++20	14 / 100	34 ms	13380 KiB

dreaming

#include "dreaming.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define dbg(x) cerr << #x << ": " << x << '\n';
#define dbgv(v) cerr << #v << ": "; for(auto &el : v) cerr << el << " "; cerr << '\n';
vector<vector<pair<int, int>>> arr;
vector<bool> vis;
void dfs(int node, int prev, int w, int &sum){
    vis[node] = 1;
    sum += w;
    for(pair<int, int> i : arr[node]){
        if(i.first == prev) continue;
        dfs(i.first, node, i.second, sum);
    }
}
void dfs2(int node, int prev, int w, ll sum, ll prevsum, int &maxn){
    int s2 = prevsum + w;
    int s1 = sum - s2;
    int ma = max(s1, s2);
    maxn = min(ma, maxn);
    for(pair<int, int> &i : arr[node]){
        if(i.first == prev) continue;
        dfs2(i.first, node, i.second, sum, s2, maxn);
    }
}
int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
    arr.assign(N, vector<pair<int, int>>());
    vis.assign(N, 0);
    for(int i = 0; i < M; i++){
        arr[A[i]].push_back({B[i], T[i]});
        arr[B[i]].push_back({A[i], T[i]});
    }
    vector<int> heads;
    for(int i = 0; i < arr.size(); i++){
        if(arr[i].size() == 1){
            heads.push_back(i);
        }
    }
    bool t = true;
    int max1 = INT_MAX, max2 = INT_MAX, sum1 = 0, sum2 = 0;
    for(int &i : heads){
        if(vis[i]) continue;
        if(t){
            dfs(i, i, 0, sum1);
            t = 0;
            dfs2(i, i, 0, sum1, 0, max1);
        } else {
            dfs(i, i, 0, sum2);
            dfs2(i, i, 0, sum2, 0, max2);
        }
    }
    return max({
        sum1, sum2, max1 + max2 + L
    });
}

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