Submission #680710

#	Time	Username	Problem	Language	Result	Execution time	Memory
680710		speedyArda	Dreaming (IOI13_dreaming)	C++14	18 / 100	64 ms	14664 KiB

dreaming

#include "dreaming.h"
#include "bits/stdc++.h"
#define pb push_back
#define pii pair<int, int>
using namespace std;
using ll = long long;
const int MAXN = 100005;
vector<vector<pair<int, int> > > adj(MAXN);
bool vis[MAXN];
pair<ll, int> down[MAXN][2];
void dfs_down(int v, int p)
{
    vis[v] = true;
    down[v][0].second = down[v][1].second = -1;

    //cout << v << "\n";
    for(pii e : adj[v])
    {
        //cout << e.first << " " << e.second << "\n";
        if(e.first == p)
            continue;
        dfs_down(e.first, v);
        ll val = down[e.first][0].first + e.second;
        if(down[v][0].first < val)
        {
            down[v][0].first = val;
            down[v][0].second = e.first;
        } else if(down[v][1].first < val)
        {
            down[v][1].first = val;
            down[v][1].second = e.first;
        }
    }

    //cout << v << " " << down[v] << "\n";
}
pair<ll, int> dfs_up(int v, int p, ll top)
{
    vis[v] = true;
    pair<ll, int> curr = {max(top, down[v][0].first), v};
    if(down[v][0].second != -1)
    {
        pii e;
        for(pii tmp : adj[v])
        {
            if(down[v][0].second == tmp.first)
                e = tmp;

        }

        pair<ll, int> temp = dfs_up(down[v][0].second, v, max(top, down[v][1].first) + e.second);
        if(curr.first > temp.first)
            curr = temp;
    }


    return curr;
}

void dfs_check(int v, int p)
{
    vis[v] = true;
    for(pii e : adj[v])
    {
        if(e.first == p)
            continue;
        dfs_check(e.first, v);
    }
}

ll ans = 0;
ll dfs_long(int v, int p)
{
    ll max_temp = 0, max_1 = 0;

    for(pii e : adj[v])
    {
        if(e.first == p)
            continue;
        ll temp = dfs_long(e.first, v) + e.second;
        max_temp = max(max_temp, max_1 + temp);
        max_1 = max(max_1, temp);
    }
    
    ans = max(ans, max_temp);
    return max_1;
}

int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
    
    for(int i = 0; i < M; i++)
    {
        adj[A[i]].pb({B[i], T[i]});
        adj[B[i]].pb({A[i], T[i]});
    }
    for(int i = 0; i < N; i++)
    {
        //cout << i << "\n";
        if(!vis[i])
            dfs_down(i, -1);
        //cout << i << "\n";
    }    

    for(int i = 0; i < N; i++)
        vis[i] = false;
    vector< pair<ll, int> > root_nodes;
    for(int i = 0; i < N; i++)
    {
        if(!vis[i])
        {
            
            //cout << i << "\n";
            pair<ll, int> temp = dfs_up(i, -1, 0);
            dfs_check(i, -1);
            //cout << i << " " << temp.first << " " << temp.second << "\n";
            root_nodes.pb(temp);
        }
    }

    sort(root_nodes.begin(), root_nodes.end());
    reverse(root_nodes.begin(), root_nodes.end());
    int from = root_nodes[0].second;
    //cout << root_nodes.size() << "\n";
    for(int i = 1; i < root_nodes.size(); i++)
    {
        int to = root_nodes[i].second;
        adj[from].pb({to, L});
        adj[to].pb({from, L});
        //cout << from << " " << to << "\n";
    }

    dfs_long(0, -1);
    return ans;

}

Compilation message (stderr)

dreaming.cpp: In function 'int travelTime(int, int, int, int*, int*, int*)':
dreaming.cpp:124:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  124 |     for(int i = 1; i < root_nodes.size(); i++)
      |                    ~~^~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 14
• Subtask 2: 0 / 10
• Subtask 3: 0 / 23
• Subtask 4: 18 / 18
• Subtask 5: 0 / 12
• Subtask 6: 0 / 23