Submission #741635

#	Time	Username	Problem	Language	Result	Execution time	Memory
741635		vjudge1	Dreaming (IOI13_dreaming)	C++17	14 / 100	232 ms	28784 KiB

dreaming

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

vector<pair<int, int> > adj[100000];
map<pair<int, int>, int> edges;
vector<int> subgraphs[100000];
bool visited[100000]={false};

void findsubgraphs(int x, int k)
{
    if (visited[x])
        return;
    visited[x]=true;
    subgraphs[k].push_back(x);
    for (auto edge : adj[x])
        if (!visited[edge.first])
            findsubgraphs(edge.first, k);

    return;
}

pair<int, int> findfarthest(int x, int t)
{
    pair<int, int> farthest={0, x};
    for (auto edge : adj[x])
    {
        int y=edge.first;
        int v=edge.second;
        if (y==t)
            continue;
        auto t=findfarthest(y, x);
        if (t.first+v>farthest.first)
            farthest={t.first+v, t.second};
    }

    return farthest;
}

bool findpath(int x, int t, int y, vector<int> &path)
{
    path.push_back(x);
    if (x==y)
        return true;
    for (auto edge : adj[x])
    {
        if (edge.first==t)
            continue;
        if (findpath(edge.first, x, y, path))
            return true;
    }
    path.pop_back();

    return false;
}

int travelTime(int n, int m, int l, int edgex[], int edgey[], int edgev[])
{
    int k=0, x, y, v, sum, maxdistance=0, i, j;
    for (i=0; i<m; i++)
    {
        x=edgex[i];
        y=edgey[i];
        v=edgev[i];
        adj[x].push_back({y, v});
        adj[y].push_back({x, v});
        edges[{x, y}]=v;
        edges[{y, x}]=v;
    }
    for (i=0; i<m; i++)
    {
        if (visited[i])
            continue;
        findsubgraphs(i, k);
        k=k+1;
    }
    pair<int, int> distances[k];
    for (i=0; i<k; i++)
    {
        x=findfarthest(subgraphs[i][0], -1).second;
        y=findfarthest(x, -1).second;
        vector<int> path;
        findpath(x, -1, y, path);
        sum=0;
        for (j=0; j<path.size()-1; j++)
            sum=sum+edges[{path[j], path[j+1]}];
        distances[i].first=0;
        distances[i].second=sum;
        for (j=0; j<path.size()-1; j++)
        {
            int nextsum1=distances[i].first+edges[{path[j], path[j+1]}];
            int nextsum2=distances[i].second-edges[{path[j], path[j+1]}];
            if (abs(nextsum1-nextsum2)>abs(distances[i].first-distances[i].second))
                break;
            distances[i].first=nextsum1;
            distances[i].second=nextsum2;
        }
        if (distances[i].second>distances[i].first)
            swap(distances[i].first, distances[i].second);
    }
    sort(distances, distances+k);
    for (i=0; i<k; i++)
        maxdistance=max(maxdistance, distances[i].first+distances[i].second);
    if (k>=2)
        maxdistance=max(maxdistance, distances[k-2].first+distances[k-1].first+l);
    if (k>=3)
        maxdistance=max(maxdistance, distances[k-2].first+distances[k-3].first+2*l);

    return maxdistance;
}

Compilation message (stderr)

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

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