Submission #478696

#	Time	Username	Problem	Language	Result	Execution time	Memory
478696		VitaliyFS	Dreaming (IOI13_dreaming)	C++17	47 / 100	133 ms	20656 KiB

dreaming

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

#define fr first
#define sc second
 
using namespace std;
//using namespace __gnu_pbds;
 
typedef long long ll;
typedef long double ld;
typedef pair<ll, ll> pll;
//typedef tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update> myset;
 
const ll DIM = 100007, INF = 2000000000000000007, MOD = 998244353, split = 1000;
 
ll t, n, m, z, q, nn,mm,kk, par[DIM], di[DIM], cl, cr, f, prev, mid, p, res2, nComp = 0, ans1, ans2, res, mi, pos, pos1, pos2, sum, ct, y, k, tt, x, t1, t2, mi1 = INF, ma1 = -INF, mi2 = INF, ma2 = -INF, v, l = INF, r = -INF, u, w, ma = -INF, id, lx, xd, yd;
bool flag;
int A[DIM], B[DIM], T[DIM];
pll comp[DIM];
vector<pll> g[DIM];
vector<ll> usedVertex;
bool used[DIM];

void dfs(ll v, ll p = -1, ll dp = 0, ll d = 0) {
    usedVertex.push_back(v);
    if(d > ma) {ma = max(ma, d); u = v;}
    used[v] = 1;
    di[v] = dp;
    par[v] = p;
    for(auto [u, w] : g[v])
        if(!used[u]) {dfs(u, v, w, d + w); z+=w;}
}

int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
    for(int i=0;i<M;++i) {
        g[A[i]].push_back({B[i], T[i]});
        g[B[i]].push_back({A[i], T[i]});
    }
    l = 0;
    for(int i =0;i<N;++i){
        if(!used[i]) {
            l++;
            usedVertex.clear();
            u = i, ma = 0, z = 0;
            dfs(i);
            for(auto u : usedVertex) used[u] = 0;
            ma = 0;
            dfs(u);
            k = 0; res = abs(ma - k); f =  u;
            while(par[u] != -1) {
                k += di[u];
                ma -= di[u];
                u = par[u];
                if(abs(k - ma) < res) {f = u; res = abs(k - ma);}
            }
            comp[l] = {f, z};

        }
    }
    f = comp[1].fr, z = comp[1].sc;
    for(int i=2;i<=l;++i){
        g[f].push_back({comp[i].fr, L});
        g[comp[i].fr].push_back({f, L});
        if(z < comp[i].sc) {f = comp[i].fr;}
        z += comp[i].sc + L;
    }
    for(int i = 0;i<N;++i) used[i] = 0;
    u = 0; ma = 0;
    dfs(u);
    for(int i=0;i<N;++i)used[i]=0;
    ma = 0, dfs(u);
    return ma;
}

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