oj.uz

Submission #292501

# Submission time Handle Problem Language Result Execution time Memory
292501 2020-09-07T06:53:08 Z daniel920712 Swapping Cities (APIO20_swap) C++14
0 / 100
 2000 ms 25696 KB 
#include "swap.h"
#include <vector>
#include <stdio.h>
#include <algorithm>
#include <queue>
#include <utility>
using namespace std;
int NN;
int MM;
int what[200005]={0};
int what2[200005];
int all[200005];
int big[200005]={0};
int deg[200005]={0};
int con[200005]={0};
bool use[200005];
bool use2[200005];

int Father[200005];
int y;
int ans=0;
vector < pair < pair < int , int > , int > > Next[200005];
vector < pair < pair < int , int > , int > > Next2[200005];
priority_queue < pair < int , int > , vector < pair < int , int > > , greater < pair < int , int >  > > dd;
struct A
{
    int u,v,w;
    int con;
}edge[200005];
vector < int > have;
bool cmp(pair < pair < int , int > , int > a,pair < pair < int , int > , int > b)
{
    return a.second<b.second;
}
bool cmp2(A a,A b)
{
    return a.w<b.w;
}
bool F(int here,int fa)
{
    what[here]=fa;
    if(here==y)
    {
        have.push_back(here);
        return 1;
    }
    for(auto i:Next2[here])
    {
        if(i.first.first==fa) continue;

        if(F(i.first.first,here))
        {
            ans=max(ans,i.first.second);
            use[i.second]=1;
            have.push_back(here);
            return 1;

        }
    }
    return 0;
}
int Find(int here)
{
    if(Father[here]==here) return here;
    Father[here]=Find(Father[here]);
    return Father[here];
}
void init(int N, int M,vector<int> U, vector<int> V, vector<int> W)
{
    NN=N;
    MM=M;
    int i;
    con[0]=N-1;
    for(i=0;i<M;i++)
    {
        Next[U[i]].push_back(make_pair(make_pair(V[i],W[i]),i));
        Next[V[i]].push_back(make_pair(make_pair(U[i],W[i]),i));

        edge[i].u=U[i];
        edge[i].v=V[i];
        edge[i].w=W[i];
        edge[i].con=i;
    }
    for(i=0;i<N;i++)
    {
        Father[i]=i;
        sort(Next[i].begin(),Next[i].end(),cmp);
    }
    sort(edge,edge+M,cmp2);
    for(i=0;i<M;i++)
    {
        if(Find(edge[i].u)==Find(edge[i].v)) continue;
        Father[Find(edge[i].u)]=Find(edge[i].v);
        Next2[edge[i].u].push_back(make_pair(make_pair(edge[i].v,edge[i].w),edge[i].con));
        Next2[edge[i].v].push_back(make_pair(make_pair(edge[i].u,edge[i].w),edge[i].con));
        //printf("%d\n",i);
    }



}

int getMinimumFuelCapacity(int x, int y)
{
    int t=2e9,t2=-1,con=0,i,j,a,b;
    ::y=y;
    for(i=0;i<MM;i++) use[i]=0;
    ans=0;
    have.clear();
    F(x,-1);
    for(auto i:have)
    {
        con=0;
        t2=-1;
        if(i==x||i==y) continue;
        for(auto j:Next[i])
        {
            if(use[j.second]) continue;
            con++;
            if(con>=1)
            {
                t2=j.first.second;
                break;
            }

        }
        if(t2!=-1) t=min(t,t2);

    }
    //for(i=0;i<MM;i++) printf("%d %d\n",i,use[i]);
    for(auto i:Next[x])
    {
        //printf("aa %d %d %d %d\n",i.first.second,i.first.second,i.second,use[i.second]);
        if(use[i.second]) continue;
        for(j=0;j<NN;j++) use2[j]=0;
        dd.push(make_pair(i.first.second,i.first.first));
        //printf("aa %d %d %d\n",i.first.second,i.first.second,i.second);
        while(!dd.empty())
        {
            a=dd.top().first;
            b=dd.top().second;
            dd.pop();
            if(use2[b]) continue;
            //printf("%d %d\n",a,b);
            if(b==y)
            {
                t=min(t,a);
                break;
            }
            use2[b]=1;
            for(auto j:Next[b])
            {
                if(j.second==i.second) continue;
                dd.push(make_pair(max(j.first.second,a),j.first.first));

            }
        }
        while(!dd.empty()) dd.pop();

    }
    if(t>=2000000000) return -1;
    //printf("%d %d\n",ans,t);
    return max(t,ans);
}

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 9728 KB Output is correct
2 Correct 7 ms 9728 KB Output is correct
3 Correct 7 ms 9728 KB Output is correct
4 Correct 8 ms 9856 KB Output is correct
5 Correct 8 ms 9856 KB Output is correct
6 Correct 8 ms 9856 KB Output is correct
7 Correct 8 ms 9856 KB Output is correct
8 Correct 8 ms 9856 KB Output is correct
9 Correct 119 ms 20572 KB Output is correct
10 Correct 186 ms 24612 KB Output is correct
11 Correct 230 ms 24856 KB Output is correct
12 Correct 211 ms 25696 KB Output is correct
13 Correct 192 ms 25308 KB Output is correct
14 Execution timed out 2087 ms 22800 KB Time limit exceeded
15 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 9728 KB Output is correct
2 Correct 7 ms 9728 KB Output is correct
3 Execution timed out 2100 ms 23504 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 9728 KB Output is correct
2 Correct 7 ms 9728 KB Output is correct
3 Correct 7 ms 9728 KB Output is correct
4 Correct 7 ms 9728 KB Output is correct
5 Correct 8 ms 9856 KB Output is correct
6 Correct 8 ms 9856 KB Output is correct
7 Correct 8 ms 9856 KB Output is correct
8 Correct 8 ms 9856 KB Output is correct
9 Correct 8 ms 9856 KB Output is correct
10 Correct 8 ms 9856 KB Output is correct
11 Correct 8 ms 9856 KB Output is correct
12 Correct 8 ms 9856 KB Output is correct
13 Correct 8 ms 9856 KB Output is correct
14 Correct 8 ms 9856 KB Output is correct
15 Incorrect 8 ms 9856 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 9728 KB Output is correct
2 Correct 7 ms 9728 KB Output is correct
3 Correct 7 ms 9728 KB Output is correct
4 Correct 7 ms 9728 KB Output is correct
5 Correct 8 ms 9856 KB Output is correct
6 Correct 8 ms 9856 KB Output is correct
7 Correct 8 ms 9856 KB Output is correct
8 Correct 8 ms 9856 KB Output is correct
9 Correct 8 ms 9856 KB Output is correct
10 Correct 119 ms 20572 KB Output is correct
11 Correct 186 ms 24612 KB Output is correct
12 Correct 230 ms 24856 KB Output is correct
13 Correct 211 ms 25696 KB Output is correct
14 Correct 192 ms 25308 KB Output is correct
15 Correct 8 ms 9856 KB Output is correct
16 Correct 8 ms 9856 KB Output is correct
17 Correct 8 ms 9856 KB Output is correct
18 Correct 8 ms 9856 KB Output is correct
19 Correct 8 ms 9856 KB Output is correct
20 Incorrect 8 ms 9856 KB Output isn't correct
21 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 9728 KB Output is correct
2 Correct 7 ms 9728 KB Output is correct
3 Correct 7 ms 9728 KB Output is correct
4 Correct 8 ms 9856 KB Output is correct
5 Correct 8 ms 9856 KB Output is correct
6 Correct 8 ms 9856 KB Output is correct
7 Correct 8 ms 9856 KB Output is correct
8 Correct 8 ms 9856 KB Output is correct
9 Correct 119 ms 20572 KB Output is correct
10 Correct 186 ms 24612 KB Output is correct
11 Correct 230 ms 24856 KB Output is correct
12 Correct 211 ms 25696 KB Output is correct
13 Correct 192 ms 25308 KB Output is correct
14 Execution timed out 2087 ms 22800 KB Time limit exceeded
15 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 9728 KB Output is correct
2 Correct 7 ms 9728 KB Output is correct
3 Correct 7 ms 9728 KB Output is correct
4 Correct 7 ms 9728 KB Output is correct
5 Correct 8 ms 9856 KB Output is correct
6 Correct 8 ms 9856 KB Output is correct
7 Correct 8 ms 9856 KB Output is correct
8 Correct 8 ms 9856 KB Output is correct
9 Correct 8 ms 9856 KB Output is correct
10 Correct 119 ms 20572 KB Output is correct
11 Correct 186 ms 24612 KB Output is correct
12 Correct 230 ms 24856 KB Output is correct
13 Correct 211 ms 25696 KB Output is correct
14 Correct 192 ms 25308 KB Output is correct
15 Execution timed out 2087 ms 22800 KB Time limit exceeded
16 Halted 0 ms 0 KB -