Submission #1038938

#	Time	Username	Problem	Language	Result	Execution time	Memory
1038938		HappyCapybara	Dreaming (IOI13_dreaming)	C++17	47 / 100	44 ms	11032 KiB

dreaming

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

vector<int> p, s;

int findp(int a){
    if (p[a] == a) return p[a];
    return p[a] = findp(p[a]);
}

void merge(int a, int b){
    a = findp(a);
    b = findp(b);
    if (a == b) return;
    p[b] = a;
    s[a] += s[b];
    s[b] == 0;
}

int travelTime(int N, int M, int L, int A[], int B[], int T[]){
    p.resize(N);
    for (int i=0; i<N; i++) p[i] = i;
    s.resize(N, 1);
    vector<vector<pair<int,int>>> g(N);
    for (int i=0; i<M; i++){
        merge(A[i], B[i]);
        g[A[i]].push_back({B[i], T[i]});
        g[B[i]].push_back({A[i], T[i]});
    }
    vector<int> dm, r;
    vector<bool> done(N, false), seen(N, false);
    vector<int> tp(N, -1), td(N);
    for (int i=0; i<N; i++){
        int j = findp(i);
        if (done[j]) continue;
        done[j] = true;
        if (s[j] == 1){
            dm.push_back(0);
            r.push_back(0);
            continue;
        }
        queue<pair<int,int>> q;
        q.push({j, 0});
        int ft = j, md = 0;
        while (!q.empty()){
            int cur = q.front().first, d = q.front().second;
            q.pop();
            if (seen[cur]) continue;
            seen[cur] = true;
            if (d > md){
                md = d;
                ft = cur;
            }
            for (pair<int,int> next : g[cur]) q.push({next.first, d+next.second});
        }
        tp[ft] = ft;
        td[ft] = 0;
        int ft2 = ft;
        md = 0;
        q.push({ft, 0});
        while (!q.empty()){
            int cur = q.front().first, d = q.front().second;
            q.pop();
            td[cur] = d;
            if (d > md){
                md = d;
                ft2 = cur;
            }
            for (pair<int,int> next : g[cur]){
                if (tp[next.first] == -1){
                    tp[next.first] = cur;
                    q.push({next.first, d+next.second});
                }
            }
        }
        dm.push_back(md);
        int br = md;
        while (ft2 != ft){
            br = min(br, max(td[ft2], md-td[ft2]));
            ft2 = tp[ft2];
        }
        r.push_back(br);
    }

    int res = 0;
    for (int x : dm) res = max(res, x);
    if (r.size() == 2) res = max(res, r[0]+r[1]+L);
    else {
        sort(r.begin(), r.end());
        res = max(res, r[r.size()-1]+r[r.size()-2]+L);
        res = max(res, r[r.size()-2]+r[r.size()-3]+2*L);
    }
    return res;
}

Compilation message (stderr)

dreaming.cpp: In function 'void merge(int, int)':
dreaming.cpp:18:10: warning: value computed is not used [-Wunused-value]
   18 |     s[b] == 0;

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