oj.uz

Submission #1097155

# Submission time Handle Problem Language Result Execution time Memory
1097155 2024-10-06T10:13:55 Z vivkostov Dreaming (IOI13_dreaming) C++14
18 / 100
 38 ms 15840 KB 
#include<bits/stdc++.h>
#define endl '\n'
#include"dreaming.h"
using namespace std;
struct cell
{
    int to,cost;
};
int n,m,l,a[200005],b[200005],t[200005],used[200005],lead[200005],dp[200005],sdp[200005],mid,mind1,mind2,mind3,sma;
vector<cell>v[200005];
void read()
{
    cin>>n>>m>>l;
    for(int i=0;i<m;i++)
    {
        cin>>a[i]>>b[i]>>t[i];
    }
}
void make_dp(int beg)
{
    used[beg]=1;
    cell w;
    for(int i=0;i<v[beg].size();i++)
    {
        w=v[beg][i];
        if(!used[w.to])
        {
            make_dp(w.to);
            if(dp[beg]<dp[w.to]+w.cost)
            {
                sdp[beg]=dp[beg];
                dp[beg]=dp[w.to]+w.cost;
            }
            else sdp[beg]=max(sdp[beg],dp[w.to]+w.cost);
        }
    }
    //sma=max(sma,dp[beg]+sdp[beg]);
}
void find_mid(int beg,int izm)
{
    used[beg]=1;
    cell w;
    int ma=0,sm=0;
    cell ind;
    ind.cost=0;
    for(int i=0;i<v[beg].size();i++)
    {
        w=v[beg][i];
        if(!used[w.to]&&dp[w.to]>ma)
        {
            ma=dp[w.to];
            ind=w;
        }
    }
    for(int i=0;i<v[beg].size();i++)
    {
        w=v[beg][i];
        if(!used[w.to]&&w.to!=ind.to&&dp[w.to]+w.cost>sm)
        {
            sm=dp[w.to]+w.cost;
        }
    }
    izm=max(izm,sm)+ind.cost;
    if(dp[beg]<=max(izm,ma))
    {
        mid=beg;
    }
    else
    {
        find_mid(w.to,izm);
    }
}
void make_lead(int beg,int le)
{
    used[beg]=2;
    lead[beg]=le;
    cell w;
    for(int i=0;i<v[beg].size();i++)
    {
        w=v[beg][i];
        if(used[w.to]<2)
        {
            make_lead(w.to,le);
        }
    }
}
void find_max_lead()
{
    int ma=-1,ind=-1;
    for(int i=0;i<n;i++)
    {
        if(ma<dp[lead[i]])
        {
            ma=dp[lead[i]];
            ind=lead[i];
        }
    }
    mind1=ind;
    ind=-1;
    ma=-1;
    for(int i=0;i<n;i++)
    {
        if(lead[i]!=mind1&&ma<dp[lead[i]])
        {
            ma=dp[lead[i]];
            ind=lead[i];
        }
    }
    mind2=ind;
    ind=-1;
    ma=-1;
    for(int i=0;i<n;i++)
    {
        if(lead[i]!=mind1&&lead[i]!=mind2&&ma<dp[lead[i]])
        {
            ma=dp[lead[i]];
            ind=lead[i];
        }
    }
    mind3=ind;
}
int get_sma(int beg,int par)
{
    cell w;
    for(int i=0;i<v[beg].size();i++)
    {
        w=v[beg][i];
        if(w.to!=par)return get_sma(w.to,beg)+w.cost;
    }
    return 0;
}
void find_sma()
{
    for(int i=0;i<n;i++)
    {
        if(v[i].size()<2)sma=max(sma,get_sma(i,i));
    }
}
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++)
    {
        a[i]=A[i];
        b[i]=B[i];
        t[i]=T[i];
        cell g;
        g.to=b[i];
        g.cost=t[i];
        v[a[i]].push_back(g);
        g.to=a[i];
        v[b[i]].push_back(g);
    }
    for(int i=0;i<n;i++)
    {
        if(!used[i])make_dp(i);
    }
    memset(used,0,sizeof(used));
    for(int i=0;i<n;i++)
    {
        if(!used[i])
        {
            find_mid(i,0);
            make_lead(i,mid);
            mid=0;
        }
    }
    memset(used,0,sizeof(used));
    memset(dp,0,sizeof(dp));
    memset(sdp,0,sizeof(sdp));
    for(int i=0;i<n;i++)
    {
        if(!used[lead[i]])make_dp(lead[i]);
    }
    find_max_lead();
    find_sma();
    if(mind2==-1)return sma;
    if(mind3==-1)return max(sma,dp[mind1]+dp[mind2]+l);
    return max(max(sma,dp[mind1]+dp[mind2]+l),dp[mind2]+dp[mind3]+2*l);
}
/*int main()
{
    read();
    cout<<travelTime(n,m,l,a,b,t)<<endl;
    return 0;
}
*/

Compilation message

dreaming.cpp: In function 'void make_dp(int)':
dreaming.cpp:23:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<cell>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   23 |     for(int i=0;i<v[beg].size();i++)
      |                 ~^~~~~~~~~~~~~~
dreaming.cpp: In function 'void find_mid(int, int)':
dreaming.cpp:46:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<cell>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   46 |     for(int i=0;i<v[beg].size();i++)
      |                 ~^~~~~~~~~~~~~~
dreaming.cpp:55:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<cell>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   55 |     for(int i=0;i<v[beg].size();i++)
      |                 ~^~~~~~~~~~~~~~
dreaming.cpp: In function 'void make_lead(int, int)':
dreaming.cpp:78:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<cell>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   78 |     for(int i=0;i<v[beg].size();i++)
      |                 ~^~~~~~~~~~~~~~
dreaming.cpp: In function 'int get_sma(int, int)':
dreaming.cpp:125:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<cell>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  125 |     for(int i=0;i<v[beg].size();i++)
      |                 ~^~~~~~~~~~~~~~
dreaming.cpp: In function 'void find_mid(int, int)':
dreaming.cpp:64:14: warning: 'w.cell::to' may be used uninitialized in this function [-Wmaybe-uninitialized]
   64 |     if(dp[beg]<=max(izm,ma))
      |        ~~~~~~^
dreaming.cpp:58:23: warning: 'ind.cell::to' may be used uninitialized in this function [-Wmaybe-uninitialized]
   58 |         if(!used[w.to]&&w.to!=ind.to&&dp[w.to]+w.cost>sm)
      |            ~~~~~~~~~~~^~~~~~~~~~~~~~

Subtask #1
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 15840 KB Output is correct
2 Correct 37 ms 15692 KB Output is correct
3 Correct 28 ms 14196 KB Output is correct
4 Correct 9 ms 8540 KB Output is correct
5 Correct 8 ms 8028 KB Output is correct
6 Correct 13 ms 9136 KB Output is correct
7 Incorrect 4 ms 7768 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

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

Subtask #3
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 15840 KB Output is correct
2 Correct 37 ms 15692 KB Output is correct
3 Correct 28 ms 14196 KB Output is correct
4 Correct 9 ms 8540 KB Output is correct
5 Correct 8 ms 8028 KB Output is correct
6 Correct 13 ms 9136 KB Output is correct
7 Incorrect 4 ms 7768 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 10328 KB Output is correct
2 Correct 18 ms 10588 KB Output is correct
3 Correct 17 ms 10332 KB Output is correct
4 Correct 16 ms 10328 KB Output is correct
5 Correct 18 ms 10332 KB Output is correct
6 Correct 18 ms 10584 KB Output is correct
7 Correct 24 ms 10588 KB Output is correct
8 Correct 16 ms 10376 KB Output is correct
9 Correct 16 ms 10488 KB Output is correct
10 Correct 17 ms 10536 KB Output is correct
11 Correct 3 ms 7516 KB Output is correct
12 Correct 5 ms 7772 KB Output is correct
13 Correct 5 ms 7772 KB Output is correct
14 Correct 6 ms 7772 KB Output is correct
15 Correct 5 ms 7772 KB Output is correct
16 Correct 5 ms 7772 KB Output is correct
17 Correct 6 ms 7772 KB Output is correct
18 Correct 7 ms 7772 KB Output is correct
19 Correct 5 ms 7772 KB Output is correct
20 Correct 3 ms 7260 KB Output is correct
21 Correct 4 ms 7260 KB Output is correct
22 Correct 5 ms 7516 KB Output is correct
23 Correct 6 ms 7924 KB Output is correct

Subtask #5
0 / 12.0

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

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 15840 KB Output is correct
2 Correct 37 ms 15692 KB Output is correct
3 Correct 28 ms 14196 KB Output is correct
4 Correct 9 ms 8540 KB Output is correct
5 Correct 8 ms 8028 KB Output is correct
6 Correct 13 ms 9136 KB Output is correct
7 Incorrect 4 ms 7768 KB Output isn't correct
8 Halted 0 ms 0 KB -