Submission #625237

#	Time	Username	Problem	Language	Result	Execution time	Memory
625237		SAAD	Dreaming (IOI13_dreaming)	C++17	77 / 100	1092 ms	14852 KiB

dreaming

#define F first
#define S second
#define rep(i,a,b) for(int i=a;!(a==b&&i!=b)&&((i<=b&&b>=a)||(i>=b&&a>=b));i+=(a<=b?1:-1))
#define pb push_back
#define Fbitl __builtin_ffs
#define bit1 __builtin_popcount
#include <iostream>
#include <math.h>
#include <algorithm>
#include <string.h>
#include <vector>
#include <queue>
#include <map>
#include <unordered_map>

using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<string, string> pss;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<pii> vii;
typedef vector<ll> vl;
typedef vector<vl> vvl;
bool visa[(int)1e6];
#include "dreaming.h"
const int Ne = 1e5 + 5;
int mx, idmx;
int mxres;
bool th = false;
vii x[Ne];
vii res;
int R;
int mn = 1e9, idmn = 1e9;
int dfs(int idx, int cst, int prnt) {
    int res = 0;
    visa[idx] = true;
    if (idx == R && th) {
        return cst;
    }
    for (auto i : x[idx]) {
        if (i.first == prnt) continue;
        res += dfs(i.first, cst + i.second, idx);
    }
    if (res > 0) {
        int mex = max(cst, mx - cst);
        if (mex < mn) {
            mn = mex;
            idmn = idx;
        }
        return cst;
    }
    if (mx < cst) {
        mx = cst;
        idmx = idx;
    }
    if (cst == 0 && !th) return idmx;
    if (th) {
        return 0;
    }
    return 0;
}
int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
    for (int i = 0; i < M; i++) {
        x[A[i]].push_back({ B[i],T[i] });
        x[B[i]].push_back({ A[i],T[i] });
    }
    for (int i = 0; i < N; i++) {
        if (visa[i]) continue;
        th = false;
        mx = 0; idmx = 0;
        int a = dfs(i, 0, -1);
        mx = 0; idmx = 0;
        int b = dfs(a, 0, -1);
        mxres = max(mxres, mx);
        if (x[i].empty()) {
            res.push_back({ 0,i });
            continue;
        }
        th = true;
        R = b;
        mn = 1e9, idmn = 1e9;
        dfs(a, 0, -1);
        res.push_back({ mn,idmn });
    }
    sort(res.begin(), res.end());
    for (int i = 0; i < res.size() - 1; i++) {
        x[res[i].second].push_back({ res[res.size() - 1].second,L });
        //cout << res[i].second << " ";
    }

    mx = 0;
    for (int i = res.size() - 1; i >= res.size() - 2 && i >= 0; i--, mx += L) {
        mx += res[i].first;
    }
    mx -= L;
    mxres = max(mxres,mx);
    if (res.size() > 2) {
        mxres = max(mxres,L*2+res[res.size()-2].first+res[res.size()-3].first);
    }
    return max(mxres, mx);
}

Compilation message (stderr)

dreaming.cpp: In function 'int travelTime(int, int, int, int*, int*, int*)':
dreaming.cpp:88:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   88 |     for (int i = 0; i < res.size() - 1; i++) {
      |                     ~~^~~~~~~~~~~~~~~~
dreaming.cpp:94:36: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   94 |     for (int i = res.size() - 1; i >= res.size() - 2 && i >= 0; i--, mx += L) {
      |                                  ~~^~~~~~~~~~~~~~~~~

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