Submission #614139

#	Time	Username	Problem	Language	Result	Execution time	Memory
614139		nohaxjustsoflo	Dreaming (IOI13_dreaming)	C++17	47 / 100	121 ms	31224 KiB

dreaming

#include <bits/stdc++.h>
#include "dreaming.h"
#include <iostream>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
typedef tree<ll,null_type,less_equal<ll>,rb_tree_tag,tree_order_statistics_node_update> order_set;
mt19937 mt_rand(chrono::high_resolution_clock::now().time_since_epoch().count());
//uniform_int_distribution<int> gen; ///(min, max)
//int random() {return gen(mt_rand);}
const int mxN=1e5+5;
const int mod=998244353;
const int mxlogN=40;
const int mxK=26;
const int inf=2e9;
const int K=600;
struct edge
{
    int u,v,w;
    int other(int i)
    {
        return i^u^v;
    }
}es[mxN];
bool vis[mxN];
vector<int> cur;
multiset<int> ms[mxN];
vector<int> adj[mxN];
int down[mxN], up[mxN];
int get_max(int i)
{
    if(ms[i].empty()) return 0;
    return *ms[i].rbegin();
}
void dfs(int i, int p)
{
    vis[i]=1;
    cur.push_back(i);
    for(int e:adj[i])
    {
        int j=es[e].other(i);
        if(j==p) continue;
        dfs(j,i);
        ms[i].insert(down[j]+es[e].w);
    }
    down[i]=get_max(i);
}
void dfs2(int i, int p)
{
    for(int e:adj[i])
    {
        int j=es[e].other(i);
        if(j==p) continue;
        ms[i].erase(ms[i].find(down[j]+es[e].w));
        up[j]=es[e].w+max(get_max(i),up[i]);
        ms[i].insert(down[j]+es[e].w);
        dfs2(j,i);
    }
}

int travelTime(int N, int M, int L, int A[], int B[], int T[])
{
    int n=N, m=M;
    for(int i=0; i<m; i++)
    {
        int u=A[i],v=B[i],w=T[i];
        es[i]={u,v,w};
        adj[u].push_back(i);
        adj[v].push_back(i);
    }
    int ans=0;
    vector<int> vs;
    for(int i=0; i<n; i++)
    {
        if(!vis[i])
        {
            dfs(i,i);
            dfs2(i,i);
            int mx=0, mn=inf;
            for(int i:cur)
            {
                mx=max(mx,max(down[i],up[i]));
                mn=min(mn,max(down[i],up[i]));
            }
            ans=max(ans,mx);
            vs.push_back(mn);
            cur.clear();
        }
    }
    sort(vs.begin(),vs.end());
    int sz=vs.size();
    if(sz<3)
    {
        if(sz==1) return ans;
        return max(ans,vs[0]+vs[1]+L);
    }
    return max(ans,vs[sz-2]+vs[sz-3]+L+L);
}
/*
int main()
{

}*/
/*
7 3
4 1 3 4 0 2 3
*/

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