oj.uz

Submission #1078466

# Submission time Handle Problem Language Result Execution time Memory
1078466 2024-08-27T17:48:01 Z alexdd Swapping Cities (APIO20_swap) C++17
0 / 100
 2000 ms 509136 KB 
#include "swap.h"
#include <bits/stdc++.h>
using namespace std;
const int BUC = 900;
//const int CNTB = 400;
const int MAXN = 100000;

struct str_DSU
{
    int father[MAXN+5],siz[MAXN+5],cap1[MAXN+5],cap2[MAXN+5],islant[MAXN+5];
    vector<pair<int*,int>> history;
    void init(int N)
    {
        for(int i=0;i<N;i++)
        {
            siz[i]=1;
            father[i]=cap1[i]=cap2[i]=i;
            islant[i]=1;
        }
    }
    int gas(int x)
    {
        if(father[x]==x)
            return x;
        return gas(father[x]);
    }
    void unite(int x, int y)
    {
        int rootx = gas(x);
        int rooty = gas(y);
        if(rootx==rooty)
        {
            if(islant[rootx])
            {
                history.push_back({&islant[rootx],islant[rootx]});
                islant[rootx]=0;
            }
            return;
        }
        if(siz[rootx] < siz[rooty])
        {
            swap(rootx,rooty);
            swap(x,y);
        }

        history.push_back({&father[y],father[y]});
        history.push_back({&siz[x],siz[x]});
        father[y]=x;
        siz[x]+=siz[y];

        if(!islant[rootx] || !islant[rooty])
        {
            if(islant[rootx])
            {
                history.push_back({&islant[rootx],islant[rootx]});
                islant[rootx]=0;
            }
        }
        else if(x==cap1[rootx] && y==cap1[rooty])
        {
            history.push_back({&cap1[rootx],cap1[rootx]});
            cap1[rootx] = cap2[rooty];
        }
        else if(x==cap1[rootx] && y==cap2[rooty])
        {
            history.push_back({&cap1[rootx],cap1[rootx]});
            cap1[rootx] = cap1[rooty];
        }
        else if(x==cap2[rootx] && y==cap1[rooty])
        {
            history.push_back({&cap2[rootx],cap2[rootx]});
            cap2[rootx] = cap2[rooty];
        }
        else if(x==cap2[rootx] && y==cap2[rooty])
        {
            history.push_back({&cap2[rootx],cap2[rootx]});
            cap2[rootx] = cap1[rooty];
        }
        else
        {
            history.push_back({&islant[rootx],islant[rootx]});
            islant[rootx]=0;
        }
    }
    void rollback(int t)
    {
        while((int)history.size() > t)
        {
            *history.back().first = history.back().second;
            history.pop_back();
        }
    }
};

vector<str_DSU> saves;
vector<int> pozs;

str_DSU dsu;
void do_save(int i, int N)
{
    //cout<<i<<" save\n";
    pozs.push_back(i);
    saves.push_back(dsu);
}
vector<pair<int,pair<int,int>>> edges;
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());
    dsu.init(N);
    do_save(-1,N);
    for(int i=0;i<M;i++)
    {
        dsu.unite(edges[i].second.first, edges[i].second.second);
        if((i+1)%BUC==0 || i==M-1)
        {
            do_save(i,N);
        }
    }
}

int getMinimumFuelCapacity(int X, int Y)
{
    int ults=0;
    for(int i=1;i<saves.size();i++)
    {
        if(saves[i].gas(X)==saves[i].gas(Y) && saves[i].islant[saves[i].gas(X)]==0)
            break;
        ults=i;
    }
    if(ults==(int)saves.size()-1)
        return -1;
    //str_DSU cop = saves[ults];///-------------------------
    int t = saves[ults].history.size();
    for(int i=pozs[ults]+1;i<edges.size();i++)
    {
        int a = edges[i].second.first, b = edges[i].second.second;
        //cout<<a<<" "<<b<<" baga\n";
        saves[ults].unite(a, b);
        if(saves[ults].gas(X)==saves[ults].gas(Y) && saves[ults].islant[saves[ults].gas(X)]==0)
        {
            saves[ults].rollback(t);
            //saves[ults] = cop;///--------------------------
            return edges[i].first;
            break;
        }
    }
    assert(1==0);
}

Compilation message

swap.cpp: In function 'int getMinimumFuelCapacity(int, int)':
swap.cpp:125:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<str_DSU>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  125 |     for(int i=1;i<saves.size();i++)
      |                 ~^~~~~~~~~~~~~
swap.cpp:135:29: 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]
  135 |     for(int i=pozs[ults]+1;i<edges.size();i++)
      |                            ~^~~~~~~~~~~~~

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 6232 KB Output is correct
2 Correct 3 ms 6232 KB Output is correct
3 Correct 3 ms 6236 KB Output is correct
4 Correct 3 ms 6236 KB Output is correct
5 Correct 7 ms 10424 KB Output is correct
6 Correct 6 ms 10424 KB Output is correct
7 Correct 6 ms 10460 KB Output is correct
8 Correct 6 ms 10424 KB Output is correct
9 Correct 290 ms 351948 KB Output is correct
10 Correct 341 ms 475772 KB Output is correct
11 Correct 368 ms 462540 KB Output is correct
12 Correct 342 ms 509136 KB Output is correct
13 Execution timed out 2070 ms 160532 KB Time limit exceeded
14 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 6232 KB Output is correct
2 Correct 3 ms 6232 KB Output is correct
3 Execution timed out 2074 ms 475768 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
0 / 17.0

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

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6232 KB Output is correct
2 Correct 4 ms 6232 KB Output is correct
3 Correct 3 ms 6232 KB Output is correct
4 Correct 3 ms 6236 KB Output is correct
5 Correct 3 ms 6236 KB Output is correct
6 Correct 7 ms 10424 KB Output is correct
7 Correct 6 ms 10424 KB Output is correct
8 Correct 6 ms 10460 KB Output is correct
9 Correct 6 ms 10424 KB Output is correct
10 Correct 290 ms 351948 KB Output is correct
11 Correct 341 ms 475772 KB Output is correct
12 Correct 368 ms 462540 KB Output is correct
13 Correct 342 ms 509136 KB Output is correct
14 Execution timed out 2070 ms 160532 KB Time limit exceeded
15 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 6232 KB Output is correct
2 Correct 3 ms 6232 KB Output is correct
3 Correct 3 ms 6236 KB Output is correct
4 Correct 3 ms 6236 KB Output is correct
5 Correct 7 ms 10424 KB Output is correct
6 Correct 6 ms 10424 KB Output is correct
7 Correct 6 ms 10460 KB Output is correct
8 Correct 6 ms 10424 KB Output is correct
9 Correct 290 ms 351948 KB Output is correct
10 Correct 341 ms 475772 KB Output is correct
11 Correct 368 ms 462540 KB Output is correct
12 Correct 342 ms 509136 KB Output is correct
13 Execution timed out 2070 ms 160532 KB Time limit exceeded
14 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6232 KB Output is correct
2 Correct 4 ms 6232 KB Output is correct
3 Correct 3 ms 6232 KB Output is correct
4 Correct 3 ms 6236 KB Output is correct
5 Correct 3 ms 6236 KB Output is correct
6 Correct 7 ms 10424 KB Output is correct
7 Correct 6 ms 10424 KB Output is correct
8 Correct 6 ms 10460 KB Output is correct
9 Correct 6 ms 10424 KB Output is correct
10 Correct 290 ms 351948 KB Output is correct
11 Correct 341 ms 475772 KB Output is correct
12 Correct 368 ms 462540 KB Output is correct
13 Correct 342 ms 509136 KB Output is correct
14 Execution timed out 2070 ms 160532 KB Time limit exceeded
15 Halted 0 ms 0 KB -