oj.uz

Submission #541074

# Submission time Handle Problem Language Result Execution time Memory
541074 2022-03-22T07:52:13 Z LittleOrange Dreaming (IOI13_dreaming) C++17
0 / 100
 53 ms 13348 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Incorrect 53 ms 13348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 53 ms 13348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 26 ms 6728 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 53 ms 13348 KB Output isn't correct
2 Halted 0 ms 0 KB -