Submission #1184612

#	Time	Username	Problem	Language	Result	Execution time	Memory
1184612		jcolada	Dreaming (IOI13_dreaming)	C++20	0 / 100	1095 ms	11328 KiB

dreaming

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

const int big = 1e5+5;
int cnt = 0, color[big] = {0}, vex[big] = {0};
bool colvis[big] = {false};
vector<vector<pair<int,int>>> adj(big);
int bag, bigdeez;
int centers[big] = {0}, par[big], wt[big];

void coldfs(int x){
    if(colvis[x]) return;
    if(color[x] == 0){cnt++; color[x] = cnt; vex[cnt] = x;}
    colvis[x] = true;
    for(auto &y : adj[x]){
        if(colvis[y.first]) continue;
        color[y.first] = color[x];
        coldfs(y.first);
    }
}

int v; long long mx;

void dfs(int x, int p, int d){
    if(d > mx){mx = d; v = x;}
    for(auto &y : adj[x]){
        if(y.first == p) continue;
        dfs(y.first, x, d + y.second);
    }
}

void dfs2(int x, int p, int d){
    par[x] = p;
    wt[x] = 0;
    if(d > mx){mx = d; v = x;}
    for(auto &y : adj[x]){
        if(y.first == p) continue;
        wt[y.first] = y.second;
        dfs(y.first, x, d + y.second);
    }
}

int travelTime(int n, int m, int l, int a[], int b[], int t[]){
    long long btt = 0; int cc;
    for(int i = 0; i < m; i++){
        adj[a[i]].push_back(make_pair(b[i],t[i]));
        adj[b[i]].push_back(make_pair(a[i],t[i]));
    }
    for (int i = 0; i < n; i++) {
        if (!colvis[i]) coldfs(i);
    }
    for(int i=1; i <= cnt; i++){
        int s = vex[i];
        mx = 0; dfs(s, -1, 0);
        mx = 0; dfs2(v, -1, 0);
        int k = v, ct = v;
        long long best = 0, curr = mx;
        while(k != -1){
            curr -= wt[k]; long long wgt = min(curr, mx - curr);
            best = max(best, wgt);
            if(best == wgt){ct = k;}
            k = par[k];
        }
        centers[i] = ct;
        if(best >= btt){btt = best; cc = ct;}
    }
    for(int i = 0; i < cnt; i++){
        if(centers[i] == cc) continue;
        adj[centers[i]].push_back(make_pair(cc, l));
        adj[cc].push_back({centers[i], l});
    }
    mx = 0; dfs(0,-1,0);
    mx = 0; dfs(v,-1,0);
    return mx;
}

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