oj.uz

Submission #292533

# Submission time Handle Problem Language Result Execution time Memory
292533 2020-09-07T08:48:18 Z daniel920712 Swapping Cities (APIO20_swap) C++14
0 / 100
 2000 ms 25820 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.first.second<b.first.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 6 ms 9728 KB Output is correct
2 Correct 6 ms 9728 KB Output is correct
3 Correct 6 ms 9728 KB Output is correct
4 Correct 7 ms 9856 KB Output is correct
5 Correct 7 ms 9856 KB Output is correct
6 Correct 7 ms 9856 KB Output is correct
7 Correct 8 ms 9856 KB Output is correct
8 Correct 7 ms 9856 KB Output is correct
9 Correct 126 ms 20648 KB Output is correct
10 Correct 189 ms 24596 KB Output is correct
11 Correct 224 ms 24860 KB Output is correct
12 Correct 224 ms 25820 KB Output is correct
13 Correct 181 ms 25388 KB Output is correct
14 Execution timed out 2082 ms 22872 KB Time limit exceeded
15 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

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

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9728 KB Output is correct
2 Correct 6 ms 9728 KB Output is correct
3 Correct 6 ms 9728 KB Output is correct
4 Correct 6 ms 9728 KB Output is correct
5 Correct 7 ms 9856 KB Output is correct
6 Correct 7 ms 9856 KB Output is correct
7 Correct 7 ms 9856 KB Output is correct
8 Correct 8 ms 9856 KB Output is correct
9 Correct 7 ms 9856 KB Output is correct
10 Correct 7 ms 9856 KB Output is correct
11 Correct 8 ms 9856 KB Output is correct
12 Correct 7 ms 9856 KB Output is correct
13 Correct 7 ms 9856 KB Output is correct
14 Correct 7 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 6 ms 9728 KB Output is correct
2 Correct 6 ms 9728 KB Output is correct
3 Correct 6 ms 9728 KB Output is correct
4 Correct 6 ms 9728 KB Output is correct
5 Correct 7 ms 9856 KB Output is correct
6 Correct 7 ms 9856 KB Output is correct
7 Correct 7 ms 9856 KB Output is correct
8 Correct 8 ms 9856 KB Output is correct
9 Correct 7 ms 9856 KB Output is correct
10 Correct 126 ms 20648 KB Output is correct
11 Correct 189 ms 24596 KB Output is correct
12 Correct 224 ms 24860 KB Output is correct
13 Correct 224 ms 25820 KB Output is correct
14 Correct 181 ms 25388 KB Output is correct
15 Correct 7 ms 9856 KB Output is correct
16 Correct 8 ms 9856 KB Output is correct
17 Correct 7 ms 9856 KB Output is correct
18 Correct 7 ms 9856 KB Output is correct
19 Correct 7 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 6 ms 9728 KB Output is correct
2 Correct 6 ms 9728 KB Output is correct
3 Correct 6 ms 9728 KB Output is correct
4 Correct 7 ms 9856 KB Output is correct
5 Correct 7 ms 9856 KB Output is correct
6 Correct 7 ms 9856 KB Output is correct
7 Correct 8 ms 9856 KB Output is correct
8 Correct 7 ms 9856 KB Output is correct
9 Correct 126 ms 20648 KB Output is correct
10 Correct 189 ms 24596 KB Output is correct
11 Correct 224 ms 24860 KB Output is correct
12 Correct 224 ms 25820 KB Output is correct
13 Correct 181 ms 25388 KB Output is correct
14 Execution timed out 2082 ms 22872 KB Time limit exceeded
15 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9728 KB Output is correct
2 Correct 6 ms 9728 KB Output is correct
3 Correct 6 ms 9728 KB Output is correct
4 Correct 6 ms 9728 KB Output is correct
5 Correct 7 ms 9856 KB Output is correct
6 Correct 7 ms 9856 KB Output is correct
7 Correct 7 ms 9856 KB Output is correct
8 Correct 8 ms 9856 KB Output is correct
9 Correct 7 ms 9856 KB Output is correct
10 Correct 126 ms 20648 KB Output is correct
11 Correct 189 ms 24596 KB Output is correct
12 Correct 224 ms 24860 KB Output is correct
13 Correct 224 ms 25820 KB Output is correct
14 Correct 181 ms 25388 KB Output is correct
15 Execution timed out 2082 ms 22872 KB Time limit exceeded
16 Halted 0 ms 0 KB -