oj.uz

Submission #1080850

# Submission time Handle Problem Language Result Execution time Memory
1080850 2024-08-29T15:07:41 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]=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++)
    {
        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)
{
    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 2 ms 2648 KB Output is correct
2 Correct 1 ms 2652 KB Output is correct
3 Correct 1 ms 2800 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 2 ms 2908 KB Output is correct
8 Correct 2 ms 2908 KB Output is correct
9 Correct 39 ms 11532 KB Output is correct
10 Correct 42 ms 13512 KB Output is correct
11 Correct 38 ms 13488 KB Output is correct
12 Correct 43 ms 14024 KB Output is correct
13 Execution timed out 2029 ms 10696 KB Time limit exceeded
14 Halted 0 ms 0 KB -

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2648 KB Output is correct
2 Correct 1 ms 2652 KB Output is correct
3 Correct 83 ms 17004 KB Output is correct
4 Correct 65 ms 17200 KB Output is correct
5 Correct 72 ms 17500 KB Output is correct
6 Correct 66 ms 17236 KB Output is correct
7 Correct 78 ms 17476 KB Output is correct
8 Correct 66 ms 17016 KB Output is correct
9 Correct 73 ms 17220 KB Output is correct
10 Correct 68 ms 17024 KB Output is correct

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2648 KB Output is correct
2 Correct 1 ms 2652 KB Output is correct
3 Correct 1 ms 2800 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 2 ms 2908 KB Output is correct
8 Correct 2 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 2 ms 2648 KB Output is correct
3 Correct 1 ms 2652 KB Output is correct
4 Correct 1 ms 2800 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 2 ms 2908 KB Output is correct
9 Correct 2 ms 2908 KB Output is correct
10 Correct 39 ms 11532 KB Output is correct
11 Correct 42 ms 13512 KB Output is correct
12 Correct 38 ms 13488 KB Output is correct
13 Correct 43 ms 14024 KB Output is correct
14 Execution timed out 2029 ms 10696 KB Time limit exceeded
15 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2648 KB Output is correct
2 Correct 1 ms 2652 KB Output is correct
3 Correct 1 ms 2800 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 2 ms 2908 KB Output is correct
8 Correct 2 ms 2908 KB Output is correct
9 Correct 39 ms 11532 KB Output is correct
10 Correct 42 ms 13512 KB Output is correct
11 Correct 38 ms 13488 KB Output is correct
12 Correct 43 ms 14024 KB Output is correct
13 Execution timed out 2029 ms 10696 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 2648 KB Output is correct
2 Correct 2 ms 2648 KB Output is correct
3 Correct 1 ms 2652 KB Output is correct
4 Correct 1 ms 2800 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 2 ms 2908 KB Output is correct
9 Correct 2 ms 2908 KB Output is correct
10 Correct 39 ms 11532 KB Output is correct
11 Correct 42 ms 13512 KB Output is correct
12 Correct 38 ms 13488 KB Output is correct
13 Correct 43 ms 14024 KB Output is correct
14 Execution timed out 2029 ms 10696 KB Time limit exceeded
15 Halted 0 ms 0 KB -