제출 #210542

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
210542		Nucleist	Dreaming (IOI13_dreaming)	C++14	14 / 100	1098 ms	23416 KiB

dreaming

#include "dreaming.h"
#include <bits/stdc++.h> 
using namespace std; 
#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
#define flash ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define debug(x) cerr << " - " << #x << ": " << x << endl;
#define debugs(x, y) cerr << " - " << #x << ": " << x << " " << #y << ": " << y << endl;
#define all(x) (x).begin(),(x).end()
#define sz(x) (ll)x.size()
#define ll long long
#define INF 1000000
#define MOD 1000000007
#define pb push_back
#define ve vector<ll>
#define dos pair<ll,ll>
#define vedos vector<dos>
#define rand mt19937 rng(chrono::steady_clock::now().time_since_epoch().count())
struct greateri
{
    template<class T>
    bool operator()(T const &a, T const &b) const { return a > b; }
};
int n;
int dp[100001];
vector<pair<int,int>>tr[100001];
bool vis[100001];
map<dos,int>ga;
int solve(int node,int p)
{
    int fat=0;
    vis[node]=1;
    for(auto it:tr[node])
    {
        if(it.first!=p)
        {
            fat=max(fat,it.second+solve(it.first,node));
        }
    }
    return dp[node]=fat;
}
int sol=0;
int ans;
set<int>kal;
void solve1(int node,int p,int besti)
{
    dp[node]=max(dp[node],besti);
    ans=min(dp[node],ans);
    set<pair<int,int>>gg;
    for(auto it:tr[node])
    {
        if(it.first!=p)
        {
            gg.insert({-(dp[it.first]+it.second),it.first});
        }
    }
    for(auto it:gg)
    {
        int p1=besti;
        int p2=0;
        auto u=it;
        gg.erase(it);
        if(gg.size()>0)
        {
        auto k =(*gg.begin());
        p2=-k.first;
        }
        if(u.second>=0 && u.second<n)solve1(u.second,node,max(p1,p2)+ga[{min(node,u.second),max(node,u.second)}]);
        gg.insert(u);
    }
    return;
}
int besti=0;
int far=0;
int nodi=0;
void dfs(int node,int p)
{
    vis[node]=1;
    if(far>besti)
    {
        besti=far;
        nodi=node;
    }
    for (auto it:tr[node])
    {
        if(it.first!=p)
            {
            far+=it.second;
            dfs(it.first,node);
            far-=it.second;
            }
    }
}
void dfs1(int node,int p)
{
    if(far>besti)
    {
        besti=far;
        nodi=node;
    }
    for (auto it:tr[node])
    {
        if(it.first!=p)
            {
            far+=it.second;
            dfs1(it.first,node);
            far-=it.second;
            }
    }
}
int diameter(int root)
{
    besti=0;
    dfs(root,-1);
    besti=0;
    dfs1(nodi,-1);
    return besti;
}
int step()
{
    int ans=0;
    memset(vis,0,sizeof vis);
    for (int i = 0; i < n; ++i)
    {
        if(!vis[i])
        {
            ans=max(ans,diameter(i));
        }
    }
    return ans;
}
int travelTime(int N,int M,int L,int A[],int B[],int T[])
{
	n=N;
	//debug(n);
	ans=pow(10,9);
    for (int i = 0; i < M; ++i)
    {
        int x=A[i];
        int y=B[i];
        int z=T[i];
        //debugs(x,y);
        tr[x].pb({y,z});
        tr[y].pb({x,z});
        ga[{min(x,y),max(x,y)}]=z;
    }
    sol=max(step(),sol);
    memset(vis,0,sizeof vis);
    for (int i = 0; i < n; ++i)
    {
        if(!vis[i])
        {
            solve(i,-1);
            solve1(i,-1,0);
            kal.insert(-ans);
            ans=pow(10,9);
        }
    }
    if(kal.size()>1)
    {
        auto u=(*kal.begin());
        kal.erase(u);
        auto k=(*kal.begin());
        sol=max(-u+L+-k,sol);
    }
    if(kal.size()>1)
    {
        auto u=(*kal.begin());
        kal.erase(u);
        auto k=(*kal.begin());
        sol=max(-u+L*2+-k,sol);
    }
    return sol;
}
//code the AC sol !
// BS/queue/map

컴파일 시 표준 에러 (stderr) 메시지

dreaming.cpp:5:0: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
 #pragma GCC optimization ("O3")
 
dreaming.cpp:6:0: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
 #pragma GCC optimization ("unroll-loops")

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