oj.uz

Submission #657839

# Submission time Handle Problem Language Result Execution time Memory
657839 2022-11-11T14:05:43 Z activedeltorre Swapping Cities (APIO20_swap) C++14
7 / 100
 1241 ms 524288 KB 
#include "swap.h"
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;
//ifstream cin("a.in");
//ofstream cout("a.out");
vector<pair<int,pair<int,int> > >edges;
bool cmp(pair<int,pair<int,int> >a,pair<int,pair<int,int> >b)
{
    return a.first<b.first;
}
vector<pair<int,long long> >adj[200005];
vector<long long>vec;
long long rasp[200005];
long long jos[200005];
long long sus[200005];
long long lvl[200005];
long long inf=1e14;
void dfs(int curr,int parent)
{
    int i,k;
    lvl[curr]=lvl[parent]+1;
    vec.clear();
    if(adj[curr].size()>=3)
    {
        for(i=0; i<adj[curr].size(); i++)
        {
            vec.push_back(adj[curr][i].second);
        }
        sort(vec.begin(),vec.end());
        jos[curr]=vec[2];
    }
    else
    {
        jos[curr]=inf;
    }
    for(i=0; i<adj[curr].size(); i++)
    {
        k=adj[curr][i].first;
        if(k!=parent)
        {
            dfs(k,curr);
        }
        jos[curr]=min(jos[curr],max(jos[curr],adj[curr][i].second));
    }
}
void dfs2(int curr,int par,long long val)
{
    int i,k;
    sus[curr]=max(min(jos[par],sus[par]),val);
    rasp[curr]=min(sus[curr],jos[curr]);
    for(i=0; i<adj[curr].size(); i++)
    {
        k=adj[curr][i].first;
        if(k!=par)
        {
            dfs2(k,curr,adj[curr][i].second);
        }
    }
}
///bl e parinte
/// drum e cost de a merge la parinte
/// ext e cost minim degreee 3
long long bl[33][200005];
long long ext[33][200005];
long long drum[33][200005];
void dfs3(int curr,int par,long long val)
{
    int i,k;
    bl[0][curr]=par;
    ext[0][curr]=min(rasp[par],rasp[curr]);
    drum[0][curr]=val;
    for(i=1; i<=30; i++)
    {
        bl[i][curr]=bl[i-1][bl[i-1][curr]];
        ext[i][curr]=min(ext[i-1][curr],ext[i-1][bl[i-1][curr]]);
        drum[i][curr]=max(drum[i-1][curr],drum[i-1][bl[i-1][curr]]);
    }
    for(i=0; i<adj[curr].size(); i++)
    {
        k=adj[curr][i].first;
        if(k!=par)
        {
            dfs3(k,curr,adj[curr][i].second);
        }
    }
}
int lca (int a,int b)
{
    int i,curr;
    if(lvl[a]<lvl[b])
    {
        swap(a,b);
    }
    for(i=30; i>=0; i--)
    {
        curr=bl[i][a];
        if(lvl[curr]>=lvl[b])
        {
            a=curr;
        }
    }
    if(a==b)
    {
        return a;
    }
    else
    {
        for(i=30; i>=0; i--)
        {
            if(bl[i][a]!=bl[i][b])
            {
                a=bl[i][a];
                b=bl[i][b];
            }
        }
        return bl[0][a];
    }
}
pair<long long,long long> calc (int a,int b)
{
    long long curr,maxdrum=0,minrel=inf,i;
    for(i=30; i>=0; i--)
    {
        curr=bl[i][a];
        if(lvl[curr]>=lvl[b])
        {
            maxdrum=max(maxdrum,drum[i][a]);
            minrel=min(minrel,ext[i][a]);
            a=curr;
        }
    }
    return make_pair(maxdrum,minrel);
}
void init(int n, int m,vector<int> a, vector<int> b, vector<int> w)
{
    int i;
    for(i=1; i<=m; i++)
    {
        a[i-1]++;
        b[i-1]++;
        adj[a[i-1]].push_back({b[i-1],w[i-1]});
        adj[b[i-1]].push_back({a[i-1],w[i-1]});
        //  edges.push_back({w[i-1],{a[i-1],b[i-1]}});
    }
    // sort(edges.begin(),edges.end(),cmp);
    sus[0]=inf;
    jos[0]=inf;
    dfs(1,0);
    dfs2(1,0,0);
    dfs3(1,0,0);
}

int getMinimumFuelCapacity(int x, int y)
{
    int lc;
    x++;
    y++;
    pair<long long,long long>a;
    pair<long long,long long>b;
    lc=lca(x,y);
    a=calc(x,lc);
    b=calc(y,lc);
    a.first=max(a.first,b.first);
    a.second=min(a.second,b.second);
    a.first=max(a.first,b.second);
    if(a.first==inf)
    {
        return -1;
    }
    else
    {
        return a.first;
    }
}
/*int main()
{
    int N, M;
    cin>>N>>M;
    vector<int> U(M), V(M), W(M);
    for (int i = 0; i < M; ++i)
    {
        cin>>U[i]>>V[i]>>W[i];
    }
    int Q;
    cin>>Q;
    vector<int> X(Q), Y(Q);
    for (int i = 0; i < Q; ++i)
    {
        cin>>X[i]>>Y[i];
    }
    init(N, M, U, V, W);
    vector<int> minimum_fuel_capacities(Q);
    for (int i = 0; i < Q; ++i)
    {
        minimum_fuel_capacities[i] = getMinimumFuelCapacity(X[i], Y[i]);
    }
    for (int i = 0; i < Q; ++i)
    {
        cout<<minimum_fuel_capacities[i]<<'\n';
    }
    return 0;
}*/

Compilation message

swap.cpp: In function 'void dfs(int, int)':
swap.cpp:27:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   27 |         for(i=0; i<adj[curr].size(); i++)
      |                  ~^~~~~~~~~~~~~~~~~
swap.cpp:38:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   38 |     for(i=0; i<adj[curr].size(); i++)
      |              ~^~~~~~~~~~~~~~~~~
swap.cpp: In function 'void dfs2(int, int, long long int)':
swap.cpp:53:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   53 |     for(i=0; i<adj[curr].size(); i++)
      |              ~^~~~~~~~~~~~~~~~~
swap.cpp: In function 'void dfs3(int, int, long long int)':
swap.cpp:80:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   80 |     for(i=0; i<adj[curr].size(); i++)
      |              ~^~~~~~~~~~~~~~~~~

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5636 KB Output is correct
2 Correct 3 ms 5588 KB Output is correct
3 Correct 3 ms 5588 KB Output is correct
4 Correct 3 ms 6024 KB Output is correct
5 Correct 4 ms 6484 KB Output is correct
6 Correct 4 ms 6356 KB Output is correct
7 Correct 4 ms 6484 KB Output is correct
8 Correct 4 ms 6484 KB Output is correct
9 Correct 227 ms 76560 KB Output is correct
10 Correct 305 ms 93792 KB Output is correct
11 Correct 263 ms 91584 KB Output is correct
12 Correct 289 ms 97168 KB Output is correct
13 Correct 305 ms 98816 KB Output is correct
14 Correct 304 ms 76136 KB Output is correct
15 Correct 1208 ms 98052 KB Output is correct
16 Correct 1231 ms 94012 KB Output is correct
17 Correct 1108 ms 102792 KB Output is correct
18 Correct 1241 ms 101532 KB Output is correct
19 Runtime error 581 ms 524288 KB Execution killed with signal 9
20 Halted 0 ms 0 KB -

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5636 KB Output is correct
2 Correct 3 ms 5588 KB Output is correct
3 Correct 881 ms 91808 KB Output is correct
4 Correct 878 ms 96120 KB Output is correct
5 Correct 924 ms 93396 KB Output is correct
6 Correct 881 ms 95720 KB Output is correct
7 Correct 915 ms 94700 KB Output is correct
8 Correct 934 ms 91244 KB Output is correct
9 Correct 895 ms 94064 KB Output is correct
10 Correct 921 ms 90500 KB Output is correct

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5636 KB Output is correct
2 Correct 3 ms 5588 KB Output is correct
3 Correct 3 ms 5588 KB Output is correct
4 Correct 3 ms 6024 KB Output is correct
5 Correct 4 ms 6484 KB Output is correct
6 Correct 4 ms 6356 KB Output is correct
7 Correct 4 ms 6484 KB Output is correct
8 Correct 4 ms 6484 KB Output is correct
9 Runtime error 315 ms 524288 KB Execution killed with signal 9
10 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 315 ms 524288 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5636 KB Output is correct
2 Correct 3 ms 5588 KB Output is correct
3 Correct 3 ms 5588 KB Output is correct
4 Correct 3 ms 6024 KB Output is correct
5 Correct 4 ms 6484 KB Output is correct
6 Correct 4 ms 6356 KB Output is correct
7 Correct 4 ms 6484 KB Output is correct
8 Correct 4 ms 6484 KB Output is correct
9 Correct 227 ms 76560 KB Output is correct
10 Correct 305 ms 93792 KB Output is correct
11 Correct 263 ms 91584 KB Output is correct
12 Correct 289 ms 97168 KB Output is correct
13 Correct 305 ms 98816 KB Output is correct
14 Correct 304 ms 76136 KB Output is correct
15 Correct 1208 ms 98052 KB Output is correct
16 Correct 1231 ms 94012 KB Output is correct
17 Correct 1108 ms 102792 KB Output is correct
18 Correct 1241 ms 101532 KB Output is correct
19 Correct 881 ms 91808 KB Output is correct
20 Correct 878 ms 96120 KB Output is correct
21 Correct 924 ms 93396 KB Output is correct
22 Correct 881 ms 95720 KB Output is correct
23 Correct 915 ms 94700 KB Output is correct
24 Correct 934 ms 91244 KB Output is correct
25 Correct 895 ms 94064 KB Output is correct
26 Correct 921 ms 90500 KB Output is correct
27 Correct 5 ms 6484 KB Output is correct
28 Incorrect 5 ms 6540 KB Output isn't correct
29 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Runtime error 315 ms 524288 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -