oj.uz

Submission #1080867

# Submission time Handle Problem Language Result Execution time Memory
1080867 2024-08-29T15:21:23 Z alexdd Swapping Cities (APIO20_swap) C++17
7 / 100
 2000 ms 17096 KB 
#include "swap.h"
#include <bits/stdc++.h>
using namespace std;
const int INF = 2e9;
int father[100005],siz[100005],cap1[100005],cap2[100005],primu[100005],insus[100005],parent[100005];
int gas(int x)
{
    if(father[x]!=x)
        father[x]=gas(father[x]);
    return father[x];
}
void unite(int x, int y, int t)
{
    int rootx = gas(x), rooty = gas(y);
    if(rootx==rooty)
    {
        primu[rootx] = min(primu[rootx], t);
        return;
    }
    if(siz[rootx] < siz[rooty])
    {
        swap(rootx,rooty);
        swap(x,y);
    }
    insus[y]=t;
    father[y]=x;
    parent[y]=x;
    siz[x]+=siz[y];

    if(primu[rootx]!=INF)
    {

    }
    else if(primu[rooty]!=INF)
    {
        primu[rootx]=t;
    }
    else if(x==cap1[rootx] && y==cap1[rooty])
    {
        cap1[rootx]=cap2[rooty];
    }
    else if(x==cap1[rootx] && y==cap2[rooty])
    {
        cap1[rootx]=cap1[rooty];
    }
    else if(x==cap2[rootx] && y==cap1[rooty])
    {
        cap2[rootx]=cap2[rooty];
    }
    else if(x==cap2[rootx] && y==cap2[rooty])
    {
        cap2[rootx]=cap1[rooty];
    }
    else
    {
        primu[rootx]=t;
    }
}

vector<pair<int,pair<int,int>>> edges;
vector<int> con[100005];
int tin[100005],tout[100005],timer;
int depth[100005];
void dfs(int nod)
{
    tin[nod]=++timer;
    for(auto adj:con[nod])
    {
        depth[adj]=depth[nod]+1;
        dfs(adj);
    }
    tout[nod]=++timer;
}
bool isanc(int x, int y)
{
    return (tin[x]<=tin[y] && tout[x]>=tout[y]);
}
void init(int N, int M, std::vector<int> U, std::vector<int> V, std::vector<int> W)
{
    for(int i=0;i<M;i++)
        edges.push_back({W[i],{U[i],V[i]}});
    sort(edges.begin(),edges.end());
    for(int i=0;i<N;i++)
    {
        parent[i]=-1;
        father[i]=i;
        siz[i]=1;
        cap1[i]=cap2[i]=i;
        primu[i]=INF;
    }
    for(int i=0;i<edges.size();i++)
    {
        unite(edges[i].second.first, edges[i].second.second, edges[i].first);
    }
    for(int i=0;i<N;i++)
        if(parent[i]!=-1)
            con[parent[i]].push_back(i);
    for(int i=0;i<N;i++)
        if(parent[i]==-1)
            dfs(i);
}

int getMinimumFuelCapacity(int x, int y)
{
    int mnm=INF,aux=0;
    while(x!=-1 && !isanc(x,y))
    {
        aux = max(aux, insus[x]);
        x = parent[x];
    }
    if(x==-1)
        return -1;
    while(y!=x)
    {
        aux = max(aux, insus[y]);
        y = parent[y];
    }
    while(x!=-1)
    {
        mnm = min(mnm, max(aux, primu[x]));
        aux = max(aux, insus[x]);
        x = parent[x];
    }
    if(mnm==INF)
        return -1;
    else
        return mnm;
}

Compilation message

swap.cpp: In function 'void init(int, int, std::vector<int>, std::vector<int>, std::vector<int>)':
swap.cpp:91:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   91 |     for(int i=0;i<edges.size();i++)
      |                 ~^~~~~~~~~~~~~

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2652 KB Output is correct
2 Correct 1 ms 2652 KB Output is correct
3 Correct 1 ms 2652 KB Output is correct
4 Correct 1 ms 2652 KB Output is correct
5 Correct 2 ms 2908 KB Output is correct
6 Correct 2 ms 2908 KB Output is correct
7 Correct 1 ms 2908 KB Output is correct
8 Correct 1 ms 2908 KB Output is correct
9 Correct 38 ms 10192 KB Output is correct
10 Correct 45 ms 11796 KB Output is correct
11 Correct 37 ms 11720 KB Output is correct
12 Correct 44 ms 12228 KB Output is correct
13 Correct 53 ms 15344 KB Output is correct
14 Correct 37 ms 10440 KB Output is correct
15 Correct 105 ms 13904 KB Output is correct
16 Correct 83 ms 13688 KB Output is correct
17 Correct 115 ms 14120 KB Output is correct
18 Execution timed out 2084 ms 17096 KB Time limit exceeded
19 Halted 0 ms 0 KB -

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2652 KB Output is correct
2 Correct 1 ms 2652 KB Output is correct
3 Correct 79 ms 13672 KB Output is correct
4 Correct 64 ms 13872 KB Output is correct
5 Correct 68 ms 13920 KB Output is correct
6 Correct 63 ms 13868 KB Output is correct
7 Correct 67 ms 13896 KB Output is correct
8 Correct 66 ms 13672 KB Output is correct
9 Correct 72 ms 13892 KB Output is correct
10 Correct 69 ms 13668 KB Output is correct

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2652 KB Output is correct
2 Correct 1 ms 2652 KB Output is correct
3 Correct 1 ms 2652 KB Output is correct
4 Correct 1 ms 2652 KB Output is correct
5 Correct 2 ms 2908 KB Output is correct
6 Correct 2 ms 2908 KB Output is correct
7 Correct 1 ms 2908 KB Output is correct
8 Correct 1 ms 2908 KB Output is correct
9 Correct 1 ms 2648 KB Output is correct
10 Incorrect 1 ms 2908 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2648 KB Output is correct
2 Correct 1 ms 2652 KB Output is correct
3 Correct 1 ms 2652 KB Output is correct
4 Correct 1 ms 2652 KB Output is correct
5 Correct 1 ms 2652 KB Output is correct
6 Correct 2 ms 2908 KB Output is correct
7 Correct 2 ms 2908 KB Output is correct
8 Correct 1 ms 2908 KB Output is correct
9 Correct 1 ms 2908 KB Output is correct
10 Correct 38 ms 10192 KB Output is correct
11 Correct 45 ms 11796 KB Output is correct
12 Correct 37 ms 11720 KB Output is correct
13 Correct 44 ms 12228 KB Output is correct
14 Correct 53 ms 15344 KB Output is correct
15 Incorrect 1 ms 2908 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2652 KB Output is correct
2 Correct 1 ms 2652 KB Output is correct
3 Correct 1 ms 2652 KB Output is correct
4 Correct 1 ms 2652 KB Output is correct
5 Correct 2 ms 2908 KB Output is correct
6 Correct 2 ms 2908 KB Output is correct
7 Correct 1 ms 2908 KB Output is correct
8 Correct 1 ms 2908 KB Output is correct
9 Correct 38 ms 10192 KB Output is correct
10 Correct 45 ms 11796 KB Output is correct
11 Correct 37 ms 11720 KB Output is correct
12 Correct 44 ms 12228 KB Output is correct
13 Correct 53 ms 15344 KB Output is correct
14 Correct 37 ms 10440 KB Output is correct
15 Correct 105 ms 13904 KB Output is correct
16 Correct 83 ms 13688 KB Output is correct
17 Correct 115 ms 14120 KB Output is correct
18 Execution timed out 2084 ms 17096 KB Time limit exceeded
19 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2648 KB Output is correct
2 Correct 1 ms 2652 KB Output is correct
3 Correct 1 ms 2652 KB Output is correct
4 Correct 1 ms 2652 KB Output is correct
5 Correct 1 ms 2652 KB Output is correct
6 Correct 2 ms 2908 KB Output is correct
7 Correct 2 ms 2908 KB Output is correct
8 Correct 1 ms 2908 KB Output is correct
9 Correct 1 ms 2908 KB Output is correct
10 Correct 38 ms 10192 KB Output is correct
11 Correct 45 ms 11796 KB Output is correct
12 Correct 37 ms 11720 KB Output is correct
13 Correct 44 ms 12228 KB Output is correct
14 Correct 53 ms 15344 KB Output is correct
15 Correct 37 ms 10440 KB Output is correct
16 Correct 105 ms 13904 KB Output is correct
17 Correct 83 ms 13688 KB Output is correct
18 Correct 115 ms 14120 KB Output is correct
19 Execution timed out 2084 ms 17096 KB Time limit exceeded
20 Halted 0 ms 0 KB -