Submission #367112

#	Time	Username	Problem	Language	Result	Execution time	Memory
367112		idk321	Dreaming (IOI13_dreaming)	C++11	0 / 100	174 ms	29756 KiB

dreaming

#include "dreaming.h"

#include <bits/stdc++.h>
using namespace std;

int n, m, l;
const int N =100005;
bool vis[N];
multiset<int> ms[N];
vector<array<int, 2>> adj[N];
vector<int> comp;

int dfs1(int node, int par)
{
    vis[node] = true;
    int res = 0;
    ms[node].insert(0);
    for (auto next : adj[node])
    {
        if (next[0] == par) continue;
        int cur = dfs1(next[0], node) + next[1];
        res = max(res, cur);
        ms[node].insert(cur);
    }

    return res;
}

int dfs2(int node, int par, int pdist)
{

    if (par != -1)
    {
        int del = *ms[node].rbegin() + pdist;
        ms[par].erase(ms[par].find(del));
        ms[node].insert(*ms[par].rbegin() + pdist);
        ms[par].insert(del);
    }
    int res = *ms[node].rbegin();


    for (auto next : adj[node])
    {

        if (next[0] == par) continue;

        res = min(res, dfs2(next[0], node, next[1]));
    }


    return res;
}


int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
    n = N;
    m = M;
    l = L;
    for (int i = 0; i < m; i++)
    {

        adj[A[i]].push_back({B[i], T[i]});
        adj[B[i]].push_back({A[i], T[i]});
    }


    for (int i = 0; i < n; i++)
    {
        if (!vis[i])
        {
            dfs1(i, -1);
            comp.push_back(dfs2(i, -1, -1));
        }
    }

    return comp[0] + comp[1] + l;
}

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