Submission #928960

#	Time	Username	Problem	Language	Result	Execution time	Memory
928960		Foolestboy	Dreaming (IOI13_dreaming)	C++14	14 / 100	44 ms	19036 KiB

dreaming

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

#define SQR(x)    (1LL * ((x) * (x)))
#define MASK(i)   (1LL << (i))
#define BIT(x, i) (((x) >> (i)) & 1)
#define fi        first
#define se        second
#define pb        push_back
#define all(x)    x.begin(), x.end()
#define rall(x)   x.rbegin(), x.rend()
#define sz(s)     (int)s.size()
#define prev      __prev
#define next      __next
#define left      __left
#define right     __right

#define mp make_pair
#define pii pair<int, int>
#define pll pair<ll, ll>
#define vi vector<int>
#define vll vector<ll>

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef unsigned int ui;

using namespace std;

const int mod = 1e9 + 7;
const int INF = 1e9 + 7;
const ll INFLL = (ll)2e18 + 7LL;
const ld PI = acos(-1);

const int dx[] = {1, -1, 0, 0, -1, 1, 1, -1};
const int dy[] = {0, 0, 1, -1, -1, -1, 1, 1};

template<class BUI, class TRONG>
    bool minimize(BUI &x, const TRONG y){
        if(x > y){
            x = y;
            return true;
        } else return false;
    }
template<class BUI, class TRONG>
    bool maximize(BUI &x, const TRONG y){
        if(x < y){
            x = y;
            return true;
        } else return false;
    }

/* Author : Bui Nguyen Duc Trong, Luong Van Chanh High School for the gifted*/
/* Template is copied by Trong */

                           /** Losing in Provincial Contests **/
                                    /** TRYING HARDER**/
                                   /**      ORZ     **/

/* -----------------[ MAIN CODE GOES HERE ]----------------- */

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const int N = 1e5 + 10;

bool vis[N];
vector<pii> adj[N];
int high[N];
int cc;
vector<int> nodes[N];
int maxVal[N];

void dfs(int u, int p, int &x){
    vis[u] = 1;
    nodes[cc].push_back(u);
    if(high[u] > high[x]) x = u;
    for(auto [v, w] : adj[u]){
        if(v == p) continue;
        high[v] = high[u] + w;
        dfs(v, u, x);
    }
}

int f[N][2];

void dfs2(int u, int p, int k){
    for(auto [v, w] : adj[u]){
        if(v == p) continue;
        f[v][k] = f[u][k] + w;
        dfs2(v, u, k);
    }
}

int travelTime(int n, int m, int len, int A[], int B[], int T[]) {
    for(int i = 0; i < m; i++){
        adj[A[i]].push_back(mp(B[i], T[i]));
        adj[B[i]].push_back(mp(A[i], T[i]));
    }
    int ans = 0;
    memset(maxVal, 0x3f, sizeof maxVal);
    for(int i = 0; i < n; i++){
        if(!vis[i]){
            ++cc;
            int x = i, y = i;
            dfs(i, 0, x);
            for(int z : nodes[cc]) high[z] = 0;
            dfs(x, 0, y);
            dfs2(x, 0, 0);
            dfs2(y, 0, 1);
            for(int z : nodes[cc]){
                maximize(ans, f[z][0] + f[z][1]);
                minimize(maxVal[cc], max(f[z][0], f[z][1]));
            }
        }
    }
    multiset<int, greater<>> st;
    for(int i = 1; i <= cc; i++) st.insert(maxVal[i]);
    int h = INF;
    for(int i = 1; i <= cc; i++){
        st.erase(st.find(maxVal[i]));
        int cost = 0;
        maximize(cost, *st.begin() + len + maxVal[i]);
        if(sz(st) > 2){
            int tmp = 0;
            auto it = st.begin();
            tmp += *(it);
            ++it;
            tmp += *(it);
            maximize(cost, 2 * len + tmp);
        }
        st.insert(maxVal[i]);
        minimize(h, cost);
    }
    maximize(ans, h);
    return ans;
}

#ifdef GNORT
void solve(){
    int n, m, len; cin >> n >> m >> len;
    int A[101], B[101], T[101];
    for(int i = 0; i < m; i++){
        cin >> A[i] >> B[i] >> T[i];
    }
    cout << travelTime(n, m, len, A, B, T) << '\n';
}

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);

    const bool multitest = 0;
    int tt = 1; if(multitest) cin >> tt;

    while( tt-- ){

        solve();

    }

    return 0;
}
#endif

Compilation message (stderr)

dreaming.cpp: In function 'void dfs(int, int, int&)':
dreaming.cpp:80:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   80 |     for(auto [v, w] : adj[u]){
      |              ^
dreaming.cpp: In function 'void dfs2(int, int, int)':
dreaming.cpp:90:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   90 |     for(auto [v, w] : adj[u]){
      |              ^

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