oj.uz

Submission #1080863

# Submission time Handle Problem Language Result Execution time Memory
1080863 2024-08-29T15:16:54 Z alexdd Swapping Cities (APIO20_swap) C++17
0 / 100
 2000 ms 11884 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);
        }
    }
    return;
    for(int i=0;i<N;i++)
    {
        if(father[i]==-1)
        {
            dfs(i);
        }
    }
}

int getMinimumFuelCapacity(int x, int y)
{
    return -1;
    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 4444 KB Output is correct
7 Correct 1 ms 4444 KB Output is correct
8 Correct 2 ms 4444 KB Output is correct
9 Correct 31 ms 10184 KB Output is correct
10 Correct 36 ms 11424 KB Output is correct
11 Correct 37 ms 11420 KB Output is correct
12 Correct 36 ms 11648 KB Output is correct
13 Execution timed out 2066 ms 9680 KB Time limit exceeded
14 Halted 0 ms 0 KB -

Subtask #2
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 Incorrect 55 ms 11884 KB Output isn't correct
4 Halted 0 ms 0 KB -

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 4444 KB Output is correct
7 Correct 1 ms 4444 KB Output is correct
8 Correct 2 ms 4444 KB Output is correct
9 Incorrect 1 ms 4444 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 4444 KB Output isn't correct
2 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 4444 KB Output is correct
7 Correct 1 ms 4444 KB Output is correct
8 Correct 2 ms 4444 KB Output is correct
9 Correct 31 ms 10184 KB Output is correct
10 Correct 36 ms 11424 KB Output is correct
11 Correct 37 ms 11420 KB Output is correct
12 Correct 36 ms 11648 KB Output is correct
13 Execution timed out 2066 ms 9680 KB Time limit exceeded
14 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 4444 KB Output isn't correct
2 Halted 0 ms 0 KB -