Submission #1183839

#	Time	Username	Problem	Language	Result	Execution time	Memory
1183839		kiwimsy	Dreaming (IOI13_dreaming)	C++20	0 / 100	1096 ms	131072 KiB

dreaming

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

using namespace std;

vector<vector<pair<ll, ll>>> adj;
vector<bool> vis, dvis;
vector<ll> diapath, diaedges;

void getpath(ll a, ll b, ll N, vector<ll> path = {}, vector<ll> edges = {}){
    path.push_back(a);
    dvis[a] = true;
    if(a == b){
        diapath = path;
        diaedges = edges;
        return;
    }
    edges.push_back(0);
    for(pair<ll, ll> i : adj[a]){
        if(!dvis[i.first]){
            edges[edges.size()-1] = i.second;
            getpath(i.first, b, N, path, edges);
        }
    }
}

void diameter(ll node, ll N){
    diapath.clear(), diaedges.clear();
    ll a = 0, b = 0, dist = 0;
    dvis = vis;
    queue<pair<ll, ll>> q;
    queue<tuple<ll, ll, ll>> qd;
    vector<ll> dia(N, -1), edges(N), parent(N);
    q.push({node, 0});
    while(!q.empty()){
        pair<ll, ll> val = q.front();
        q.pop();
        if(dvis[val.first]) continue;
        for(pair<ll, ll> i : adj[val.first]){
            if(!dvis[i.first]){
                q.push({i.first, i.second + val.second});
                if(i.second + val.second > dist){
                    a = i.first;
                    dist = i.second + val.second;
                }
            }
        }
        dvis[val.first] = true;
    }
    qd.push({a, 0, 0});
    dvis = vis, dist = 0;
    dia[0] = a;
    while(!qd.empty()){
        tuple<ll, ll, ll> val = qd.front();
        qd.pop();
        if(dvis[get<0>(val)]) continue;
        for(pair<ll, ll> i : adj[get<0>(val)]){
            if(!dvis[i.first]){
                qd.push({i.first, get<1>(val) + 1, i.second + get<2>(val)});
                if(i.second + get<2>(val) > dist){
                    dist = i.second + get<2>(val);
                    b = i.first;
                }
            }
        }
        dvis[get<0>(val)] = true;
    }
    dvis = vis;
    getpath(a, b, N);
    vis = dvis;
}

int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
    adj.resize(N);
    ll ret = 0, bigcenter = 0, maxdia = 0;
    vector<ll> centers;
    for(ll i = 0; i < M; i++){
        adj[A[i]].push_back({B[i], T[i]});
        adj[B[i]].push_back({A[i], T[i]});
    }
    vis.assign(N, false);
    for(ll i = 0; i < N; i++){
        if(!vis[i]){
            diameter(i, N);
            vis[i] = true;
            ll c = i, c1 = i, c2 = i, w1 = 0, w2 = 0, dialength = 0;
            for(ll j : diaedges) dialength += j;
            if(dialength > 0){
                for(ll j = 1; w1 <= dialength / 2; j++){
                    c1 = diapath[j];
                    w1 += diaedges[j-1];
                }
                for(ll j = diapath.size() - 1; w2 <= dialength / 2; j--){
                    c2 = diapath[j];
                    if(j+1 < diaedges.size()) w2 += diapath[j+1];
                }
                if(w1 > w2) c = c2;
                else c = c1;
            }
            if(dialength > maxdia){
                bigcenter = c;
                maxdia = dialength;
            }
            centers.push_back(c);
        }
    }
    for(ll i : centers){
        if(i != bigcenter){
            adj[i].push_back({bigcenter, L});
            adj[bigcenter].push_back({i, L});
        }
    }
    vis.assign(N, false);
    diameter(0, N);
    for(ll i : diaedges) ret += i;
    return ret;
}

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