Submission #541074

#	Time	Username	Problem	Language	Result	Execution time	Memory
541074		LittleOrange	Dreaming (IOI13_dreaming)	C++17	0 / 100	53 ms	13348 KiB

dreaming

#include"dreaming.h"
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
struct line{
    int to;
    int time;
    int s = 0;
};
int gr(int i, vector<int> &root){
    if (root[i] == i) return i;
    else return root[i] = gr(root[i], root);
}
int dfs(int i, int p, vector<vector<line>> &connect, vector<int> &big, vector<bool> &used){
    used[i] = true;
    int r = 0;
    for (line &l : connect[i]){
        if (l.to == p) continue;
        l.s = l.time + dfs(l.to,i, connect, big, used);
        r = max(r,l.s);
    }
    big[i] = r;
    return r;
}
void dfs2(int i, int p, int b, vector<vector<line>> &connect, vector<int> &big){
    for (line &l : connect[i]){
        if (l.to == p) {
            l.s = l.time + b;
            big[i] = max(big[i],l.s);
        }
    }
    for (line &l : connect[i]){
        if (l.to != p) {
            dfs2(l.to,i,big[i],connect,big);
        }
    }
}
int travelTime(int n,int M,int L, int A[],int B[],int T[]){
    vector<vector<line>> connect(n);
    vector<int> root(n);
    for (int i = 0;i<n;i++){
        root[i] = i;
    }
    for (int i = 0;i<M;i++){
        connect[A[i]].push_back({B[i],T[i]});
        connect[B[i]].push_back({A[i],T[i]});
        root[gr(B[i],root)] = gr(A[i],root);
    }
    vector<bool> used(n,false);
    vector<int> big(n,0);
    vector<int> chunk(n,n*10000);
    for (int i = 0;i<n;i++){
        if (!used[i]){
            dfs(i,-1, connect, big, used);
            dfs2(i,-1,0,connect,big);
        }
        chunk[gr(i,root)] = min(chunk[gr(i,root)],big[i]);
    }
    vector<int> m;
    for (int i = 0;i<n;i++){
        if (chunk[gr(i,root)]==big[i]){
            m.push_back(big[i]);
        }
    }
    int ans = 0;
    for (int i = 0;i<n;i++){
        ans = max(ans,big[i]);
    }
    sort(m.begin(),m.end());
    if (m.size()>1){
        ans = max(ans,m[m.size()-1]+m[m.size()-2]+L);
        if (m.size()>2){
            ans = max(ans,m[m.size()-3]+m[m.size()-2]+L+L);
        }
    }
    return ans;
}

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