oj.uz

Submission #645552

# Submission time Handle Problem Language Result Execution time Memory
645552 2022-09-27T10:29:24 Z Tenis0206 Swapping Cities (APIO20_swap) C++11
0 / 100
 264 ms 43940 KB 
#include <bits/stdc++.h>

using namespace std;

const int oo = INT_MAX;

vector<pair<int,int>> G[100005];
vector<pair<int,pair<int,int>>> e;

vector<int> l[100005];
vector<pair<int,int>> c[100005];

int t[100005];
int Max[100005];

multiset<int> s[100005];

int reprezentant(int nod)
{
    if(t[nod]==nod)
    {
        return nod;
    }
    return reprezentant(t[nod]);
}

void uneste(int x, int y, int cost)
{
    x = reprezentant(x);
    y = reprezentant(y);
    if(x==y)
    {
        return;
    }
    auto itx = s[x].lower_bound(cost);
    s[x].erase(itx);
    auto ity = s[y].lower_bound(cost);
    s[y].erase(ity);
    if(l[x].size() > l[y].size())
    {
        t[y] = x;
        for(auto it=s[y].begin();it!=s[y].end();it++)
        {
            s[x].insert(*it);
        }
        Max[x] = max(Max[x],cost);
        Max[x] = max(Max[x],Max[y]);
        auto it = s[x].begin();
        int val = 0;
        if(it==s[x].end())
        {
            val = oo;
        }
        else
        {
            val = *it;
        }
        val = max(val,Max[x]);
        for(auto it : l[y])
        {
            l[x].push_back(it);
            c[it].push_back({x,val});
        }
    }
    else
    {
        t[x] = y;
        for(auto it=s[x].begin();it!=s[x].end();it++)
        {
            s[y].insert(*it);
        }
        Max[y] = max(Max[y],cost);
        Max[y] = max(Max[y],Max[x]);
        auto it =s[y].begin();
        int val = 0;
        if(it==s[y].end())
        {
            val = oo;
        }
        else
        {
            val = *it;
        }
        val = max(val,Max[y]);
        for(auto it : l[x])
        {
            l[y].push_back(it);
            c[it].push_back({y,val});
        }
    }
}

void init(int n, int m, vector<int> u, vector<int> v, vector<int> w)
{
    for(int i=0;i<m;i++)
    {
        int x = u[i];
        int y = v[i];
        int c = w[i];
        e.push_back({c,{x,y}});
        G[x].push_back({y,c});
        G[y].push_back({x,c});
    }
    sort(e.begin(),e.end());
    for(int i=0;i<n;i++)
    {
        t[i] = i;
        Max[i] = 0;
        for(auto it : G[i])
        {
            int c = it.second;
            s[i].insert(c);
        }
        auto it = s[i].begin();
        l[i].push_back(i);
        c[i].push_back({i,*it});
    }
    for(auto it : e)
    {
        int x = it.second.first;
        int y = it.second.second;
        int c = it.first;
        uneste(x,y,c);
    }
    for(int i=0;i<n;i++)
    {
        reverse(c[i].begin(),c[i].end());
    }
}

int getMinimumFuelCapacity(int x, int y)
{
    int st = 0;
    int dr = min(c[x].size(),c[y].size()) - 1;
    int poz = 0;
    while(st<=dr)
    {
        int mij = (st + dr) >> 1;
        if(c[x][mij].first==c[y][mij].first)
        {
            poz = mij;
            st = mij + 1;
        }
        else
        {
            dr = mij - 1;
        }
    }
    if(c[x][poz].second==oo || c[y][poz].second==oo)
    {
        return -1;
    }
    return max(c[x][poz].second,c[y][poz].second);
}

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 11988 KB Output is correct
2 Correct 7 ms 11988 KB Output is correct
3 Incorrect 6 ms 11952 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 11988 KB Output is correct
2 Correct 7 ms 11988 KB Output is correct
3 Incorrect 264 ms 43940 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 11988 KB Output is correct
2 Correct 7 ms 11988 KB Output is correct
3 Incorrect 6 ms 11952 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 11988 KB Output is correct
2 Correct 7 ms 11988 KB Output is correct
3 Incorrect 6 ms 11952 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 11988 KB Output is correct
2 Correct 7 ms 11988 KB Output is correct
3 Incorrect 6 ms 11952 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 11988 KB Output is correct
2 Correct 7 ms 11988 KB Output is correct
3 Incorrect 6 ms 11952 KB Output isn't correct
4 Halted 0 ms 0 KB -