Submission #1184270

#	Time	Username	Problem	Language	Result	Execution time	Memory
1184270		kiwimsy	Dreaming (IOI13_dreaming)	C++20	100 / 100	63 ms	10464 KiB

dreaming

#include "dreaming.h"
#include <bits/stdc++.h>
#define ll long long

using namespace std;

vector<vector<pair<int, int>>> adj;
vector<bool> vis, comp;
vector<int> diapath, diaedges;
vector<int> parent;

pair<ll, ll> get_furthest(int node, int N){
    vis.assign(N, false);
    queue<pair<int, int>> q;
    vector<pair<int, int>> nodes;
    ll dist = 0, ret = node;
    q.push({node, 0});
    while(!q.empty()){
        pair<int, int> val = q.front();
        nodes.push_back(val);
        vis[val.first] = true;
        comp[val.first] = true;
        q.pop();
        if(val.second > dist){
            ret = val.first;
            dist = val.second;
        }
        for(pair<int, int> i : adj[val.first]){
            if(!vis[i.first]){
                parent[i.first] = val.first;
                q.push({i.first, i.second + val.second});
            }
        }
    }
    return {ret, dist};
}

ll diameter(int node, int N){
    diapath.clear(), diaedges.clear();
    int a, b, p;
    pair<int, int> dia;
    a = get_furthest(node, N).first;
    dia = get_furthest(a, N);
    b = dia.first;
    p = b;
    while(p != a){
        diapath.push_back(p);
        for(pair<int, int> i : adj[p]) if(i.first == parent[p]) diaedges.push_back(i.second);
        p = parent[p];
    }
    diapath.push_back(a);
    return dia.second;
}

int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
    adj.resize(N), parent.resize(N), comp.resize(N);
    int bigcenter = -1, maxrad = -1;
    vector<int> centers;
    for(int i = 0; i < M; i++){
        adj[A[i]].push_back({B[i], T[i]});
        adj[B[i]].push_back({A[i], T[i]});
    }
    for(int i = 0; i < N; i++){
        if(!comp[i]){
            ll dialength = max(diameter(i, N), 0ll);
            ll c = i, p = 0, mindist = dialength;
            if(dialength > 0){
                for(int j = 0; j < diapath.size(); j++){
                    if(max(p, dialength - p) < mindist){
                        c = diapath[j];
                        mindist = max(p, dialength - p);
                    }
                    if(j < diaedges.size()) p += diaedges[j];
                }
            }
            if(mindist > maxrad){
                bigcenter = c;
                maxrad = mindist;
            }
            // cerr << endl << "center at " << c << endl;
            centers.push_back(c);
        }
    }
    for(int i : centers){
        if(i != bigcenter){
            // cerr << i << ' ';
            adj[i].push_back({bigcenter, L});
            adj[bigcenter].push_back({i, L});
        }
    }
    // cerr << endl;
    ll ret = diameter(0, N);
    return ret;
}

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