oj.uz

Submission #206928

# Submission time Handle Problem Language Result Execution time Memory
206928 2020-03-06T00:08:30 Z oko Dreaming (IOI13_dreaming) C++14
0 / 100
 98 ms 21496 KB 
#include<bits/stdc++.h>

#include "dreaming.h"
using namespace std;
const long long mod=1e9+7;

long long n,m,l,st1,st2,vis[100005],mn=1e10,dis[100005];
vector<pair<int,int> >gr[100005];
void dfs(int x)
{
    vis[x]=1;
    for(int i=0;i<gr[x].size();i++)
    {
        int u=gr[x][i].first;
        if(vis[u])continue;
        dfs(u);
    }
}
void cal(int x)
{
    vis[x]=1;
    for(int i=0;i<gr[x].size();i++)
    {
        int u=gr[x][i].first,w=gr[x][i].second;
        if(vis[u])continue;
        cal(u);
        dis[x]=max(dis[x],dis[u]+w);
    }
}
void root(int x)
{
    vis[x]=1;
    mn=min(mn,dis[x]);
    multiset<int>ms;
    ms.insert(0);
    for(int i=0;i<gr[x].size();i++)
    {
        int u=gr[x][i].first,w=gr[x][i].second;
        ms.insert(dis[u]+w);
    }
    for(int i=0;i<gr[x].size();i++)
    {
        int u=gr[x][i].first,w=gr[x][i].second;
        if(vis[u])continue;
        ms.erase(ms.lower_bound(dis[u]+w));
        long long oldx=dis[x],oldu=dis[u];
        dis[x]=*--ms.end();
        dis[u]=max(dis[u],dis[x]+w);
        root(u);
        dis[x]=oldx;
        dis[u]=oldu;
        ms.insert(dis[u]+w);
    }
}
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++)
    {
        gr[A[i]+1].push_back({B[i]+1,T[i]});
        gr[B[i]+1].push_back({A[i]+1,T[i]});
    }
    for(int i=1;i<=n;i++)
    {
        if(vis[i]==0&&st1==0)
        {
            dfs(i);
            st1=i;
        }
        if(vis[i]==0&&st1)
        {
            dfs(i);
            st2=i;
        }
    }
    memset(vis,0,sizeof vis);
    cal(st1);
    memset(vis,0,sizeof vis);
    root(st1);
    long long ans=mn;

    mn=1e10;
    memset(vis,0,sizeof vis);
    cal(st2);
    memset(vis,0,sizeof vis);
    root(st2);

    return max(dis[st1],max(dis[st2],ans+mn+l));
}

Compilation message

dreaming.cpp: In function 'void dfs(int)':
dreaming.cpp:12:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<gr[x].size();i++)
                 ~^~~~~~~~~~~~~
dreaming.cpp: In function 'void cal(int)':
dreaming.cpp:22:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<gr[x].size();i++)
                 ~^~~~~~~~~~~~~
dreaming.cpp: In function 'void root(int)':
dreaming.cpp:36:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<gr[x].size();i++)
                 ~^~~~~~~~~~~~~
dreaming.cpp:41:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<gr[x].size();i++)
                 ~^~~~~~~~~~~~~

Subtask #1
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 98 ms 21496 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 98 ms 21496 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 98 ms 21496 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 25 ms 5752 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 98 ms 21496 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 98 ms 21496 KB Output isn't correct
2 Halted 0 ms 0 KB -