oj.uz

Submission #645553

# Submission time Handle Problem Language Result Execution time Memory
645553 2022-09-27T10:30:12 Z Tenis0206 Swapping Cities (APIO20_swap) C++11
0 / 100
 339 ms 44928 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)
{
    return -1;
    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 8 ms 11988 KB Output is correct
3 Correct 8 ms 12016 KB Output is correct
4 Correct 7 ms 12116 KB Output is correct
5 Correct 7 ms 12244 KB Output is correct
6 Correct 8 ms 12244 KB Output is correct
7 Correct 9 ms 12244 KB Output is correct
8 Correct 7 ms 12292 KB Output is correct
9 Correct 219 ms 36764 KB Output is correct
10 Correct 279 ms 41608 KB Output is correct
11 Correct 260 ms 41188 KB Output is correct
12 Correct 303 ms 43016 KB Output is correct
13 Correct 193 ms 37592 KB Output is correct
14 Correct 237 ms 36900 KB Output is correct
15 Correct 314 ms 43996 KB Output is correct
16 Correct 324 ms 43112 KB Output is correct
17 Correct 339 ms 44928 KB Output is correct
18 Correct 253 ms 39424 KB Output is correct
19 Incorrect 69 ms 20044 KB Output isn't correct
20 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 8 ms 11988 KB Output is correct
3 Incorrect 239 ms 41404 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 8 ms 11988 KB Output is correct
3 Correct 8 ms 12016 KB Output is correct
4 Correct 7 ms 12116 KB Output is correct
5 Correct 7 ms 12244 KB Output is correct
6 Correct 8 ms 12244 KB Output is correct
7 Correct 9 ms 12244 KB Output is correct
8 Correct 7 ms 12292 KB Output is correct
9 Incorrect 6 ms 11988 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 11988 KB Output isn't correct
2 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 8 ms 11988 KB Output is correct
3 Correct 8 ms 12016 KB Output is correct
4 Correct 7 ms 12116 KB Output is correct
5 Correct 7 ms 12244 KB Output is correct
6 Correct 8 ms 12244 KB Output is correct
7 Correct 9 ms 12244 KB Output is correct
8 Correct 7 ms 12292 KB Output is correct
9 Correct 219 ms 36764 KB Output is correct
10 Correct 279 ms 41608 KB Output is correct
11 Correct 260 ms 41188 KB Output is correct
12 Correct 303 ms 43016 KB Output is correct
13 Correct 193 ms 37592 KB Output is correct
14 Correct 237 ms 36900 KB Output is correct
15 Correct 314 ms 43996 KB Output is correct
16 Correct 324 ms 43112 KB Output is correct
17 Correct 339 ms 44928 KB Output is correct
18 Correct 253 ms 39424 KB Output is correct
19 Incorrect 239 ms 41404 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

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