Submission #336038

#	Time	Username	Problem	Language	Result	Execution time	Memory
336038		knightron0	Dreaming (IOI13_dreaming)	C++14	0 / 100	106 ms	15612 KiB

dreaming

#include <bits/stdc++.h>
#include "dreaming.h"
#define pb push_back
#define mp make_pair
#define fr first
#define sc second
#define clr(a) memset(a, 0, sizeof(a))
#define all(v) v.begin(), v.end()

using namespace std;
const int MOD = 1e9 + 7;
const int MAXN = 1e5 + 5;

int dist[MAXN];
vector<pair<int, int> > adj[MAXN];
int n, m, k;
int mx;
int val;
bool vis[MAXN][10]; 
vector<int> nice;

void dfs(int s, int curr, int fl, bool ad){

    vis[s][fl] = true;
    if(curr >= mx){
        mx = curr;
        val = s;
    }
    if(ad){
        dist[s] = max(curr, dist[s]);
    } else {
        nice.pb(s);
    }
    for(auto it: adj[s]){
        if(!vis[it.fr][fl]){
            dfs(it.fr, curr + it.sc, fl, ad);
        }
    }
}
int travelTime(int N,int M,int L, int A[],int B[],int T[]){
    n = N; m = M; k = L;
    for(int i= 0;i<m;i++){
        adj[A[i]].pb(mp(B[i], T[i]));
        adj[B[i]].pb(mp(A[i], T[i]));
    }
    clr(dist);
    vector<pair<int, int> > vec;
    for(int i = 0;i<n;i++){
        if(vis[i][0]) continue;
        nice.clear();
        mx = 0;
        val = -1;
        dfs(i, 0, 0, 0);
        int d1 = val;
        mx = 0;
        val = -1;
        dfs(d1, 0, 1, 1);
        int d2 = val;
        mx = 0;
        val = -1;
        dfs(d2, 0, 2, 1);
        int ok = 0;
        int mxval=INT_MAX;
        for(int j: nice){
            if(dist[j] <= mxval){
                mxval = dist[j];
                ok = j;
            }
        }
        vec.pb(mp(dist[ok], ok));
    }
    sort(all(vec));
    reverse(all(vec));
    for(int i= 1;i<(int)vec.size();i++){
        adj[vec[0].sc].pb(mp(vec[i].sc, k));
    }
    mx = 0;
    val = -1;
    dfs(1, 0, 4, 0);
    int d1 = val; mx = 0; val = -1;
    dfs(d1, 0, 5, 1);
    return mx;
}
// signed main() {
//     ios_base::sync_with_stdio(false);
//     cin.tie(NULL);
//     #ifndef ONLINE_JUDGE
//     freopen("input.txt", "r", stdin);
//     #endif
    
//     return 0;
// }

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