Submission #492181

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
492181	2021-12-05T20:27:54 Z	aci	Dreaming (IOI13_dreaming)	C++14	Compilation error	0 ms	0 KB

dreaming

#include <bits/stdc++.h>
#include "dreaming.h"
using namespace std;
#define INF 1000000000
typedef long long ll;
typedef pair<ll, ll> pi;

vector<vector<pi>> t;
vector<bool> used;
vector<bool> used2;


int n, m, l;
ll d, r;
vector<pi> dist;
vector<int> el;

void dfs1(int u, int p)
{
    used[u] = 1;
    el.push_back(u);
    for (pi v : t[u])
    {
        if(v.first!=p && !used[v.first])
        {
            dist[v.first].first = dist[u].first + v.second;
            dfs1(v.first, u);
        }
    }
}

void dfs2(int u, int p)
{
    used2[u] = 1;
    for (pi v : t[u])
    {
        if(v.first!=p && !used2[v.first])
        {
            dist[v.first].second = dist[u].second + v.second;
            dfs2(v.first, u);
        }
    }
}
void dfs3(int u, int p)
{
    used2[u] = 1;
    for (pi v : t[u])
    {
        if(v.first!=p && !used2[v.first])
        {
            dist[v.first].first = dist[u].first + v.second;
            dfs3(v.first, u);
        }
    }
}

bool cmp(pi a, pi b)
{
    
    return (a.second > b.second);
}


int travelTime(int N, int M, int L, int A[], int B[], int T[]) 
{
    
    n = N;
    m = M;
    l = L;

    t.resize(n);
    used.resize(n, 0);
    dist.resize(n, {-1, -1});
    used2.resize(n, 0);

    for (int i=0; i<m; i++)
    {
        int x, y, w;
        x = A[i];
        y = B[i];
        w = T[i];

        t[x].push_back({y, w});
        t[y].push_back({x, w});
    }

    vector<pi> comp; //diametro massimo e profondità

    for (int i=0; i<n; i++)
    {
        
        if(!used[i])
        {
            
            dist[i].first =0;//parto nodo a caso
            el.clear(); 
            dfs1(i, i);
            
            used2.assign(n, 0); //rifaccio dfs
            int ind=i, mx = 0;
            
            //cerco nodo a distanza massima 
            for (int j : el)
            {
                if(dist[j].first > mx)
                {
                    mx = dist[j].first;
                    ind = j;
                }
            }


            dist[ind].second = 0;
            dfs2(ind, ind);
            
            d = 0;
            //trovo diamentro e suoi estremi
            for (int j : el)
            {
                if(dist[j].second > d)
                {
                    d = dist[j].second;
                    ind = j;
                }
            }
            //rifaccio fs anche su altro estremo
            used2.assign(n, 0);
            dist[ind].first = 0;
            r = INF;
            dfs3(ind, ind);
            //for (int j : el) //cout<<j<<" "<< dist[j].first<<" "<<dist[j].second<<endl;
            for (int j : el)
            {
                if(dist[j].first==-1) dist[j].first = INF;
                if(dist[j].second==-1) dist[j].second = INF;
                r = min(r, max(dist[j].first, dist[j].second));
            }
            comp.push_back({d, r});

        }
    }
    
    sort(comp.begin(), comp.end(), cmp);
    long long res = 0;
    for (auto x : comp) res = max(res, x.first); 
    ll a, b;
    if(comp.size()==1) a = 0;
    else a = comp[0].second+l+comp[1].second;
    if(comp.size()==2) b = 0;
    else b = 2*l+comp[1].second+comp[2].second);
    res = max(res, max( a, b);

    //for (auto x : comp) //cout<< x.first<<" "<<x.second<<endl;


    return res;

}

Compilation message

dreaming.cpp: In function 'int travelTime(int, int, int, int*, int*, int*)':
dreaming.cpp:150:47: error: expected ';' before ')' token
  150 |     else b = 2*l+comp[1].second+comp[2].second);
      |                                               ^
      |                                               ;
dreaming.cpp:151:30: error: expected ')' before ';' token
  151 |     res = max(res, max( a, b);
      |              ~               ^
      |                              )