oj.uz

Submission #530892

# Submission time Handle Problem Language Result Execution time Memory
530892 2022-02-27T04:53:12 Z ToroTN Dreaming (IOI13_dreaming) C++14
14 / 100
 55 ms 9280 KB 
#include<bits/stdc++.h>
using namespace std;
#include "dreaming.h"
int mx1=-1e9,mx2=-1e9,sum,val,n,m,l,u_i,v_i,w_i,d1[100005],d2[100005],u,y,ans=1e9,cost,mx,p[100005],lst,st,md,ed,sup,suck=-1e9;
vector<pair<int,int> > v[100005];
vector<int> path,g;
queue<int> q;
void bfs(int x)
{
    q.push(x);
    d1[x]=0;
    mx=-1;
    while(!q.empty())
    {
        u=q.front();
        q.pop();
        if(d1[u]>mx)
        {
            mx=d1[u];
            x=u;
        }
        for(int i=0;i<v[u].size();i++)
        {
            y=v[u][i].first;
            cost=v[u][i].second;
            if(d1[y]==-1)
            {
                d1[y]=d1[u]+cost;
                q.push(y);
            }
        }
    }
    mx=-1;
    d2[x]=0;
    p[x]=0;
    q.push(x);
    while(!q.empty())
    {
        u=q.front();
        q.pop();
        if(d2[u]>mx)
        {
            mx=d2[u];
            lst=u;
        }
        for(int i=0;i<v[u].size();i++)
        {
            y=v[u][i].first;
            cost=v[u][i].second;
            if(d2[y]==-1)
            {
                p[y]=u;
                d2[y]=d2[u]+cost;
                q.push(y);
            }
        }
    }
    path.clear();
    g.clear();
    while(1)
    {
        if(lst==0)
        {
            break;
        }
        path.push_back(lst);
        if(p[lst]!=0)
        {
            g.push_back(d2[lst]-d2[p[lst]]);
        }
        lst=p[lst];
    }
}
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++)
    {
        u_i=A[i]+1;
        v_i=B[i]+1;
        w_i=T[i];
        v[u_i].push_back({v_i,w_i});
        v[v_i].push_back({u_i,w_i});
    }
    memset(d1,-1,sizeof d1);
    memset(d2,-1,sizeof d2);
    for(int i=1;i<=n;i++)
    {
        if(d1[i]==-1)
        {
            bfs(i);
            /*for(int j=0;j<path.size();j++)
            {
                printf("%d ",path[j]);
            }
            printf("\n");
            for(int j=0;j<g.size();j++)
            {
                printf("%d ",g[j]);
            }
            printf("\n");*/
            val=1e9;
            for(int j=0;j<g.size();j++)
            {
                sum+=g[j];
            }
            suck=max(suck,sum);
            sup=0;
            val=min(val,max(sup,sum));
            for(int j=0;j<g.size();j++)
            {
                sup+=g[j];
                sum-=g[j];
                val=min(val,max(sup,sum));
            }
            if(val>=mx1)
            {
                mx2=mx1;
                mx1=val;
            }else if(val>=mx2)
            {
                mx2=val;
            }
        }
    }
    //printf("%d %d\n",mx1,mx2);
    if(mx1==0&&mx2==0)
    {
        return 2*l;
    }else
    {
        if(mx2==-1e9)
        {
            return suck;
        }else
        {
            return max(suck,mx1+mx2+l);
        }
    }
}

Compilation message

dreaming.cpp: In function 'void bfs(int)':
dreaming.cpp:22:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   22 |         for(int i=0;i<v[u].size();i++)
      |                     ~^~~~~~~~~~~~
dreaming.cpp:46:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   46 |         for(int i=0;i<v[u].size();i++)
      |                     ~^~~~~~~~~~~~
dreaming.cpp: In function 'int travelTime(int, int, int, int*, int*, int*)':
dreaming.cpp:104:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  104 |             for(int j=0;j<g.size();j++)
      |                         ~^~~~~~~~~
dreaming.cpp:111:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  111 |             for(int j=0;j<g.size();j++)
      |                         ~^~~~~~~~~

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 8768 KB Output is correct
2 Correct 55 ms 9280 KB Output is correct
3 Correct 28 ms 7412 KB Output is correct
4 Correct 11 ms 4400 KB Output is correct
5 Correct 8 ms 4044 KB Output is correct
6 Correct 11 ms 4940 KB Output is correct
7 Correct 2 ms 3424 KB Output is correct
8 Correct 19 ms 6112 KB Output is correct
9 Correct 26 ms 6948 KB Output is correct
10 Correct 2 ms 3424 KB Output is correct
11 Correct 40 ms 7912 KB Output is correct
12 Correct 50 ms 8808 KB Output is correct
13 Correct 3 ms 3404 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3404 KB Output is correct
2 Correct 2 ms 3404 KB Output is correct
3 Correct 2 ms 3404 KB Output is correct
4 Correct 2 ms 3404 KB Output is correct
5 Correct 2 ms 3420 KB Output is correct
6 Correct 2 ms 3428 KB Output is correct
7 Correct 2 ms 3404 KB Output is correct
8 Correct 2 ms 3404 KB Output is correct
9 Correct 2 ms 3404 KB Output is correct
10 Correct 2 ms 3404 KB Output is correct
11 Correct 3 ms 3404 KB Output is correct
12 Correct 2 ms 3384 KB Output is correct
13 Correct 2 ms 3404 KB Output is correct
14 Correct 2 ms 3404 KB Output is correct
15 Incorrect 3 ms 3404 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #3
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 8768 KB Output is correct
2 Correct 55 ms 9280 KB Output is correct
3 Correct 28 ms 7412 KB Output is correct
4 Correct 11 ms 4400 KB Output is correct
5 Correct 8 ms 4044 KB Output is correct
6 Correct 11 ms 4940 KB Output is correct
7 Correct 2 ms 3424 KB Output is correct
8 Correct 19 ms 6112 KB Output is correct
9 Correct 26 ms 6948 KB Output is correct
10 Correct 2 ms 3424 KB Output is correct
11 Correct 40 ms 7912 KB Output is correct
12 Correct 50 ms 8808 KB Output is correct
13 Correct 3 ms 3404 KB Output is correct
14 Correct 2 ms 3404 KB Output is correct
15 Correct 2 ms 3404 KB Output is correct
16 Correct 2 ms 3404 KB Output is correct
17 Correct 2 ms 3404 KB Output is correct
18 Correct 2 ms 3420 KB Output is correct
19 Correct 2 ms 3428 KB Output is correct
20 Correct 2 ms 3404 KB Output is correct
21 Correct 2 ms 3404 KB Output is correct
22 Correct 2 ms 3404 KB Output is correct
23 Correct 2 ms 3404 KB Output is correct
24 Correct 3 ms 3404 KB Output is correct
25 Correct 2 ms 3384 KB Output is correct
26 Correct 2 ms 3404 KB Output is correct
27 Correct 2 ms 3404 KB Output is correct
28 Incorrect 3 ms 3404 KB Output isn't correct
29 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 6092 KB Output is correct
2 Incorrect 21 ms 6144 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3404 KB Output is correct
2 Correct 2 ms 3404 KB Output is correct
3 Correct 2 ms 3404 KB Output is correct
4 Correct 2 ms 3404 KB Output is correct
5 Correct 2 ms 3420 KB Output is correct
6 Correct 2 ms 3428 KB Output is correct
7 Correct 2 ms 3404 KB Output is correct
8 Correct 2 ms 3404 KB Output is correct
9 Correct 2 ms 3404 KB Output is correct
10 Correct 2 ms 3404 KB Output is correct
11 Correct 3 ms 3404 KB Output is correct
12 Correct 2 ms 3384 KB Output is correct
13 Correct 2 ms 3404 KB Output is correct
14 Correct 2 ms 3404 KB Output is correct
15 Incorrect 3 ms 3404 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 8768 KB Output is correct
2 Correct 55 ms 9280 KB Output is correct
3 Correct 28 ms 7412 KB Output is correct
4 Correct 11 ms 4400 KB Output is correct
5 Correct 8 ms 4044 KB Output is correct
6 Correct 11 ms 4940 KB Output is correct
7 Correct 2 ms 3424 KB Output is correct
8 Correct 19 ms 6112 KB Output is correct
9 Correct 26 ms 6948 KB Output is correct
10 Correct 2 ms 3424 KB Output is correct
11 Correct 40 ms 7912 KB Output is correct
12 Correct 50 ms 8808 KB Output is correct
13 Correct 3 ms 3404 KB Output is correct
14 Correct 2 ms 3404 KB Output is correct
15 Correct 2 ms 3404 KB Output is correct
16 Correct 2 ms 3404 KB Output is correct
17 Correct 2 ms 3404 KB Output is correct
18 Correct 2 ms 3420 KB Output is correct
19 Correct 2 ms 3428 KB Output is correct
20 Correct 2 ms 3404 KB Output is correct
21 Correct 2 ms 3404 KB Output is correct
22 Correct 2 ms 3404 KB Output is correct
23 Correct 2 ms 3404 KB Output is correct
24 Correct 3 ms 3404 KB Output is correct
25 Correct 2 ms 3384 KB Output is correct
26 Correct 2 ms 3404 KB Output is correct
27 Correct 2 ms 3404 KB Output is correct
28 Incorrect 3 ms 3404 KB Output isn't correct
29 Halted 0 ms 0 KB -