oj.uz

Submission #741626

# Submission time Handle Problem Language Result Execution time Memory
741626 2023-05-14T13:25:57 Z vjudge1 Dreaming (IOI13_dreaming) C++17
14 / 100
 221 ms 29812 KB 
#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, bool valid, 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, valid, 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, false, 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);
    maxdistance=distances[k-1].first+distances[k-1].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

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.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 185 ms 28584 KB Output is correct
2 Correct 202 ms 29812 KB Output is correct
3 Correct 120 ms 21328 KB Output is correct
4 Correct 18 ms 8612 KB Output is correct
5 Correct 16 ms 7324 KB Output is correct
6 Correct 33 ms 10528 KB Output is correct
7 Correct 4 ms 5076 KB Output is correct
8 Correct 86 ms 14576 KB Output is correct
9 Correct 116 ms 17836 KB Output is correct
10 Correct 3 ms 5136 KB Output is correct
11 Correct 195 ms 22348 KB Output is correct
12 Correct 221 ms 26128 KB Output is correct
13 Correct 4 ms 5204 KB Output is correct

Subtask #2
0 / 10.0

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

Subtask #3
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 185 ms 28584 KB Output is correct
2 Correct 202 ms 29812 KB Output is correct
3 Correct 120 ms 21328 KB Output is correct
4 Correct 18 ms 8612 KB Output is correct
5 Correct 16 ms 7324 KB Output is correct
6 Correct 33 ms 10528 KB Output is correct
7 Correct 4 ms 5076 KB Output is correct
8 Correct 86 ms 14576 KB Output is correct
9 Correct 116 ms 17836 KB Output is correct
10 Correct 3 ms 5136 KB Output is correct
11 Correct 195 ms 22348 KB Output is correct
12 Correct 221 ms 26128 KB Output is correct
13 Correct 4 ms 5204 KB Output is correct
14 Correct 3 ms 4948 KB Output is correct
15 Correct 3 ms 5004 KB Output is correct
16 Correct 3 ms 4948 KB Output is correct
17 Correct 3 ms 4948 KB Output is correct
18 Correct 3 ms 4948 KB Output is correct
19 Correct 3 ms 5008 KB Output is correct
20 Correct 3 ms 4948 KB Output is correct
21 Correct 3 ms 4948 KB Output is correct
22 Correct 3 ms 5004 KB Output is correct
23 Correct 3 ms 5076 KB Output is correct
24 Correct 3 ms 4948 KB Output is correct
25 Correct 3 ms 5000 KB Output is correct
26 Correct 3 ms 4948 KB Output is correct
27 Correct 3 ms 4948 KB Output is correct
28 Incorrect 2 ms 5004 KB Output isn't correct
29 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 61 ms 12364 KB Output is correct
2 Incorrect 55 ms 12356 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

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

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 185 ms 28584 KB Output is correct
2 Correct 202 ms 29812 KB Output is correct
3 Correct 120 ms 21328 KB Output is correct
4 Correct 18 ms 8612 KB Output is correct
5 Correct 16 ms 7324 KB Output is correct
6 Correct 33 ms 10528 KB Output is correct
7 Correct 4 ms 5076 KB Output is correct
8 Correct 86 ms 14576 KB Output is correct
9 Correct 116 ms 17836 KB Output is correct
10 Correct 3 ms 5136 KB Output is correct
11 Correct 195 ms 22348 KB Output is correct
12 Correct 221 ms 26128 KB Output is correct
13 Correct 4 ms 5204 KB Output is correct
14 Correct 3 ms 4948 KB Output is correct
15 Correct 3 ms 5004 KB Output is correct
16 Correct 3 ms 4948 KB Output is correct
17 Correct 3 ms 4948 KB Output is correct
18 Correct 3 ms 4948 KB Output is correct
19 Correct 3 ms 5008 KB Output is correct
20 Correct 3 ms 4948 KB Output is correct
21 Correct 3 ms 4948 KB Output is correct
22 Correct 3 ms 5004 KB Output is correct
23 Correct 3 ms 5076 KB Output is correct
24 Correct 3 ms 4948 KB Output is correct
25 Correct 3 ms 5000 KB Output is correct
26 Correct 3 ms 4948 KB Output is correct
27 Correct 3 ms 4948 KB Output is correct
28 Incorrect 2 ms 5004 KB Output isn't correct
29 Halted 0 ms 0 KB -