oj.uz

답안 #210556

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
210556 2020-03-17T17:03:17 Z Nucleist 꿈 (IOI13_dreaming) C++14
0 / 100
 1000 ms 30968 KB 
#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],dp1[100001];
vector<pair<int,int>>tr[100001];
bool vis[100001];
map<dos,int>ga;
int solve(int node,int p)
{
	//debug(node);
    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)
{
	debug(node);
    dp1[node]=max(dp[node],besti);
    ans=min(dp1[node],ans);
    set<pair<int,int>>gg,gg1;
    for(auto it:tr[node])
    {
        if(it.first!=p)
        {
            gg.insert({-(dp[it.first]+it.second),it.first});
        }
    }
    gg1=gg;
    for(auto it:gg)
    {
        int p1=besti;
        int p2=0;
        auto u=it;
        gg1.erase(it);
        if(gg1.size()>0)
        {
        auto k =(*gg1.begin());
        p2=-k.first;
        }
        //debug(u.second);
        if(u.second>=0 && u.second<n && u.second!=p)solve1(u.second,node,max(p1,p2)+ga[{min(node,u.second),max(node,u.second)}]);
        gg1.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[])
{
	//flash;
	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

Compilation message

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
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1088 ms 30968 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1088 ms 30968 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1088 ms 30968 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1050 ms 9568 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1088 ms 30968 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1088 ms 30968 KB Time limit exceeded
2 Halted 0 ms 0 KB -