제출 #427734

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
427734		arayi	꿈 (IOI13_dreaming)	C++17	100 / 100	139 ms	47484 KiB

dreaming

#include "dreaming.h"
#include <bits/stdc++.h>
#define ad push_back
#define MP make_pair
#define sc second
#define fr first
using namespace std;

const int N = 1e6 + 30;
int n;
vector<pair<int, int> > g[N];
bool col[N];
int dp[N][2], ans;
void dfs0(int v)
{
    col[v]=1;
    for(auto p : g[v])
    {
        if(col[p.fr]) continue;
        dfs0(p.fr);
        dp[v][0] = max(dp[v][0], dp[p.fr][0] + p.sc);
    }
}
int dfs(int v)
{
    ans = max(ans, dp[v][0] + dp[v][1]);
    int ret = max(dp[v][0], dp[v][1]);
    col[v]=0;
    vector<int> fp;
    for(auto p : g[v])
    {
        if(!col[p.fr]) continue;
        dp[p.fr][1] = dp[v][1] + p.sc;
        fp.ad(dp[p.fr][0] + p.sc);
    }
    if(fp.size() > 1)
    {
        sort(fp.begin(), fp.end());
        swap(fp[0], fp[fp.size() - 2]);
        for(auto p : g[v])
        {
            if(!col[p.fr]) continue;
            if(dp[p.fr][0] + p.sc == fp.back()) dp[p.fr][1] = max(dp[p.fr][1], p.sc + fp[0]);
            else dp[p.fr][1] = max(dp[p.fr][1], p.sc + fp.back());
        }
    }
    for(auto p : g[v])
    {
        if(!col[p.fr]) continue;
        ret = min(ret, dfs(p.fr));
    }
    return ret;
}

int travelTime(int N, int M, int L, int A[], int B[], int T[])
{
    vector <int> fp;
    n = N;
    for(int i = 0; i < M; i++)
    {
        g[A[i]].ad(MP(B[i], T[i]));
        g[B[i]].ad(MP(A[i], T[i]));
    }
    for(int i = 0; i < n; i++)
        if(!col[i]) dfs0(i);
    for(int i = 0; i < n; i++)
        if(col[i]) fp.ad(dfs(i));
    sort(fp.begin(), fp.end());
    reverse(fp.begin(), fp.end());
    if(fp.size() > 1)
    {
        ans = max(ans, fp[0] + fp[1] + L);
        if(fp.size() > 2) ans = max(ans, fp[1] + fp[2] + L*2);
    }
    return ans;
}

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