Submission #1254668

#	Time	Username	Problem	Language	Result	Execution time	Memory
1254668		anarch_y	Dreaming (IOI13_dreaming)	C++20	47 / 100	52 ms	15560 KiB

dreaming

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define all(x) begin(x), end(x)
#define sz(x) (int)x.size()
#define pb push_back
#include "dreaming.h";

const int maxn = 100001;
vector<pair<int, int>> adj[maxn];
bool vis[maxn];
int d[maxn];
pair<int, int> par[maxn];
vector<int> v;

void dfs(int s, int p, int w){
    par[s] = {p, w};
    d[s] = d[p] + w;
    vis[s] = true;
    v.pb(s);
    for(auto [u, ww]: adj[s]){
        if(u == p) continue;
        dfs(u, s, ww);
    }
}

int travelTime(int N, int M, int L, int A[], int B[], int T[]){
    for(int i=0; i<M; i++){
        int a = A[i], b = B[i], c = T[i];
        a++; b++;
        adj[a].pb({b, c}); adj[b].pb({a, c});
    }
    vector<vector<int>> vec;
    for(int i=1; i<=N; i++){
        if(!vis[i]){
            dfs(i, 0, 0);
            int mx = 0;
            for(auto j: v){
                mx = max(mx, d[j]);
            }
            int a = 0;
            for(auto j: v){
                if(d[j] == mx){
                    a = j;
                    break;
                }
            }
            v.clear();
            dfs(a, 0, 0);
            mx = 0;
            for(auto j: v){
                mx = max(mx, d[j]);
            }
            int b = 0;
            for(auto j: v){
                if(d[j] == mx){
                    b = j;
                    break;
                }
            }
            v.clear();
            vector<int> v1;
            int c = b;
            while(c != a){
                int w = par[c].second;
                v1.pb(w);
                c = par[c].first;
            }
            if(sz(v1) == 0){
                vec.pb({0, 0, 0});
            }
            else{
                int x = 0, y = 0;
                for(auto w: v1) y += w;
                for(auto w: v1){
                    if(x <= y and x+w >= y-w){
                        vec.pb({x, w, y-w});
                        break;
                    }
                    x += w;
                    y -= w;
                }
            }
        }
    }
    auto f = [&](vector<int> v1, vector<int> v2){
        int x1 = v1[0], w1 = v1[1], y1 = v1[2];
        int x2 = v2[0], w2 = v2[1], y2 = v2[2];
        int a = min(x1+w1, y1+w1);
        int b = min(x2+w2, y2+w2);
        int d1 = x1 + w1 + y1;
        int d2 = x2 + w2 + y2;
        int d3 = a + b + L;
        if(d1 == max({d1, d2, d3})) return v1;
        if(d2 == max({d1, d2, d3})) return v2;
        if(a <= b){
            if(a+L >= b) return vector<int>({a, L, b});
            else return vector<int>({a+L, w2, b-w2});
        }
        else{
            if(b+L >= a) return vector<int>({b, L, a});
            else return vector<int>({b+L, w1, a-w1});
        }    
    };
    vector<int> ans = vec[0];
    for(int i=1; i<sz(vec); i++){
        ans = f(ans, vec[i]);
    }
    return ans[0] + ans[1] + ans[2];
}

Compilation message (stderr)

dreaming.cpp:7:22: warning: extra tokens at end of #include directive
    7 | #include "dreaming.h";
      |                      ^

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