oj.uz

Submission #586552

# Submission time Handle Problem Language Result Execution time Memory
586552 2022-06-30T11:37:47 Z yutabi Dreaming (IOI13_dreaming) C++14
18 / 100
 43 ms 15180 KB 
#include "dreaming.h"

#include <bits/stdc++.h>
using namespace std;

#define pb push_back

typedef pair <int,int> ii;



vector <vector <ii> > forest;
vector <bool> v;

int m;
int m_loc;

void DFS(int node, int curr=0, int par=-1)
{
    v[node]=1;

    if(curr>=m)
    {
        m=curr;

        m_loc=node;
    }

    for(int i=0;i<forest[node].size();i++)
    {
        if(forest[node][i].first!=par)
        {
            DFS(forest[node][i].first,curr+forest[node][i].second,node);
        }
    }

    return;
}

vector <int> P;

int DFS2(int node, int g, int par=-1)
{
    if(node==g)
    {
        int sum=0;

        for(int i=0;i<P.size();i++)
        {
            sum+=P[i];
        }

        int ans=sum;

        int sum2=0;

        for(int i=0;i<P.size();i++)
        {
            sum2+=P[i];

            ans=min(ans,max(sum-sum2,sum2));
        }

        P.clear();

        return ans;
    }

    for(int i=0;i<forest[node].size();i++)
    {
        if(forest[node][i].first!=par)
        {
            P.pb(forest[node][i].second);

            int res=DFS2(forest[node][i].first,g,node);

            if(res!=-1)
            {
                return res;
            }

            P.pop_back();
        }
    }

    return -1;
}

int travelTime(int N, int M, int L, int A[], int B[], int T[])
{
    v=vector <bool> (N,0);

    forest=vector <vector <ii> > (N);

    vector <int> ans;

    for(int i=0;i<M;i++)
    {
        forest[A[i]].pb(ii(B[i],T[i]));
        forest[B[i]].pb(ii(A[i],T[i]));
    }

    for(int i=0;i<N;i++)
    {
        if(v[i]==0)
        {
            m=0;

            DFS(i);

            int p1=m_loc;

            m=0;

            DFS(p1);

            int p2=m_loc;

            ans.pb(DFS2(p1,p2));

            //printf("%d\n",ans.back());
        }
    }

    sort(ans.begin(),ans.end());

    if(ans.size()==1)
    {
        return ans[0];
    }

    if(ans.size()==2)
    {
        return ans[0]+ans[1]+L;
    }

    return max(ans[ans.size()-1]+ans[ans.size()-2]+L,ans[ans.size()-2]+ans[ans.size()-3]+L+L);
}

Compilation message

dreaming.cpp: In function 'void DFS(int, int, int)':
dreaming.cpp:29:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   29 |     for(int i=0;i<forest[node].size();i++)
      |                 ~^~~~~~~~~~~~~~~~~~~~
dreaming.cpp: In function 'int DFS2(int, int, int)':
dreaming.cpp:48:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   48 |         for(int i=0;i<P.size();i++)
      |                     ~^~~~~~~~~
dreaming.cpp:57:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   57 |         for(int i=0;i<P.size();i++)
      |                     ~^~~~~~~~~
dreaming.cpp:69:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   69 |     for(int i=0;i<forest[node].size();i++)
      |                 ~^~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 14.0

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

Subtask #2
0 / 10.0

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

Subtask #3
0 / 23.0

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

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 5640 KB Output is correct
2 Correct 21 ms 5656 KB Output is correct
3 Correct 27 ms 5584 KB Output is correct
4 Correct 26 ms 5668 KB Output is correct
5 Correct 20 ms 5588 KB Output is correct
6 Correct 25 ms 6196 KB Output is correct
7 Correct 28 ms 5800 KB Output is correct
8 Correct 22 ms 5516 KB Output is correct
9 Correct 18 ms 5428 KB Output is correct
10 Correct 19 ms 5820 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 6 ms 3252 KB Output is correct
13 Correct 8 ms 3324 KB Output is correct
14 Correct 5 ms 3280 KB Output is correct
15 Correct 5 ms 3280 KB Output is correct
16 Correct 5 ms 3280 KB Output is correct
17 Correct 4 ms 3280 KB Output is correct
18 Correct 4 ms 3280 KB Output is correct
19 Correct 8 ms 3280 KB Output is correct
20 Correct 1 ms 212 KB Output is correct
21 Correct 0 ms 308 KB Output is correct
22 Correct 1 ms 340 KB Output is correct
23 Correct 6 ms 3280 KB Output is correct

Subtask #5
0 / 12.0

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

Subtask #6
0 / 23.0

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