oj.uz

Submission #1079465

# Submission time Handle Problem Language Result Execution time Memory
1079465 2024-08-28T15:11:34 Z alexdd Swapping Cities (APIO20_swap) C++17
7 / 100
 2000 ms 17500 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];
int gas(int x)
{
    if(father[x]==x)
        return x;
    return gas(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;
    siz[x]+=siz[y];

    if(primu[rootx]!=INF)
    {

    }
    else if(primu[rooty]!=INF)
    {
        primu[rootx]=primu[rooty];
    }
    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++)
    {
        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(father[i]==i)
        {
            father[i]=-1;
        }
        else
        {
            con[father[i]].push_back(i);
        }
    }
    for(int i=0;i<N;i++)
    {
        if(father[i]==-1)
        {
            dfs(i);
        }
    }
}

int getMinimumFuelCapacity(int x, int y)
{
    if(depth[x] < depth[y])
        swap(x,y);
    int mnm=INF,aux=0;
    while(x!=-1 && !isanc(x,y))
    {
        aux = max(aux, insus[x]);
        x = father[x];
    }
    if(x==-1)
        return -1;
    while(y!=x)
    {
        aux = max(aux, insus[y]);
        y = father[y];
    }
    while(x!=-1)
    {
        mnm = min(mnm, max(aux, primu[x]));
        aux = max(aux, insus[x]);
        x = father[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:89: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]
   89 |     for(int i=0;i<edges.size();i++)
      |                 ~^~~~~~~~~~~~~

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Correct 1 ms 4444 KB Output is correct
5 Correct 1 ms 4444 KB Output is correct
6 Correct 1 ms 4440 KB Output is correct
7 Correct 1 ms 4444 KB Output is correct
8 Correct 2 ms 4700 KB Output is correct
9 Correct 31 ms 11856 KB Output is correct
10 Correct 40 ms 13512 KB Output is correct
11 Correct 39 ms 13588 KB Output is correct
12 Correct 38 ms 14024 KB Output is correct
13 Execution timed out 2040 ms 11788 KB Time limit exceeded
14 Halted 0 ms 0 KB -

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 61 ms 17260 KB Output is correct
4 Correct 72 ms 17316 KB Output is correct
5 Correct 62 ms 17500 KB Output is correct
6 Correct 62 ms 17200 KB Output is correct
7 Correct 69 ms 17476 KB Output is correct
8 Correct 61 ms 17332 KB Output is correct
9 Correct 66 ms 17224 KB Output is correct
10 Correct 63 ms 17280 KB Output is correct

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Correct 1 ms 4444 KB Output is correct
5 Correct 1 ms 4444 KB Output is correct
6 Correct 1 ms 4440 KB Output is correct
7 Correct 1 ms 4444 KB Output is correct
8 Correct 2 ms 4700 KB Output is correct
9 Correct 1 ms 4444 KB Output is correct
10 Incorrect 2 ms 4444 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 4444 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Correct 1 ms 4444 KB Output is correct
5 Correct 1 ms 4444 KB Output is correct
6 Correct 1 ms 4444 KB Output is correct
7 Correct 1 ms 4440 KB Output is correct
8 Correct 1 ms 4444 KB Output is correct
9 Correct 2 ms 4700 KB Output is correct
10 Correct 31 ms 11856 KB Output is correct
11 Correct 40 ms 13512 KB Output is correct
12 Correct 39 ms 13588 KB Output is correct
13 Correct 38 ms 14024 KB Output is correct
14 Execution timed out 2040 ms 11788 KB Time limit exceeded
15 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Correct 1 ms 4444 KB Output is correct
5 Correct 1 ms 4444 KB Output is correct
6 Correct 1 ms 4440 KB Output is correct
7 Correct 1 ms 4444 KB Output is correct
8 Correct 2 ms 4700 KB Output is correct
9 Correct 31 ms 11856 KB Output is correct
10 Correct 40 ms 13512 KB Output is correct
11 Correct 39 ms 13588 KB Output is correct
12 Correct 38 ms 14024 KB Output is correct
13 Execution timed out 2040 ms 11788 KB Time limit exceeded
14 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Correct 1 ms 4444 KB Output is correct
5 Correct 1 ms 4444 KB Output is correct
6 Correct 1 ms 4444 KB Output is correct
7 Correct 1 ms 4440 KB Output is correct
8 Correct 1 ms 4444 KB Output is correct
9 Correct 2 ms 4700 KB Output is correct
10 Correct 31 ms 11856 KB Output is correct
11 Correct 40 ms 13512 KB Output is correct
12 Correct 39 ms 13588 KB Output is correct
13 Correct 38 ms 14024 KB Output is correct
14 Execution timed out 2040 ms 11788 KB Time limit exceeded
15 Halted 0 ms 0 KB -