oj.uz

Submission #292510

# Submission time Handle Problem Language Result Execution time Memory
292510 2020-09-07T07:40:19 Z daniel920712 Swapping Cities (APIO20_swap) C++14
0 / 100
 2000 ms 25948 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];
bool have2[200005];
bool have3[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);
        have2[here]=1;
        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);
            have2[here]=1;
            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));
    }
}

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;
    for(i=0;i<=NN;i++) have2[i]=0;
    ans=0;
    have.clear();
    F(x,-1);
    for(auto i:have)
    {
        con=0;
        t2=-1;

        for(auto j:Next[i])
        {
            if(use[j.second]) continue;
            if(i==x||i==y) continue;
            con++;
            if((i!=x&&i!=y&&con>=1)||con>=2)
            {
                t2=j.first.second;
                break;
            }

        }
        if(t2!=-1) t=min(t,t2);
    }
    for(auto i:Next[x])
    {
        if(use[i.second]) continue;

        for(j=0;j<=NN;j++) use2[j]=0;
        for(j=0;j<=MM;j++) have3[j]=0;
        have3[i.second]=1;
        dd.push(make_pair(i.first.second,i.first.first));
        while(!dd.empty())
        {
            a=dd.top().first;
            b=dd.top().second;
            dd.pop();
            if(use2[b])
            {
                t=min(t,a);
                break;
            }
            if(have2[b])
            {
                t=min(t,a);
                break;
            }
            use2[b]=1;
            for(auto j:Next[b])
            {
                if(have3[j.second]) continue;
                have3[j.second]=1;
                dd.push(make_pair(max(j.first.second,a),j.first.first));

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

    }

    /*for(auto i:Next[y])
    {
        if(use[i.second]) continue;

        for(j=0;j<=NN;j++) use2[j]=0;
        for(j=0;j<=MM;j++) have3[j]=0;
        have3[i.second]=1;
        dd.push(make_pair(i.first.second,i.first.first));
        while(!dd.empty())
        {
            a=dd.top().first;
            b=dd.top().second;
            dd.pop();
            if(use2[b])
            {
                t=min(t,a);
                break;
            }
            if(have2[b])
            {
                t=min(t,a);
                break;
            }
            use2[b]=1;
            for(auto j:Next[b])
            {
                if(have3[j.second]) continue;
                have3[j.second]=1;
                dd.push(make_pair(max(j.first.second,a),j.first.first));

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

    }*/
    if(t>=2000000000) return -1;
    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 7 ms 9856 KB Output is correct
5 Correct 7 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 7 ms 9856 KB Output is correct
9 Correct 121 ms 20828 KB Output is correct
10 Correct 181 ms 24848 KB Output is correct
11 Correct 230 ms 25008 KB Output is correct
12 Correct 215 ms 25948 KB Output is correct
13 Correct 182 ms 25564 KB Output is correct
14 Execution timed out 2083 ms 23024 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 2069 ms 23636 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 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 8 ms 9856 KB Output is correct
9 Correct 7 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 7 ms 9856 KB Output is correct
14 Correct 8 ms 9856 KB Output is correct
15 Incorrect 7 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 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 8 ms 9856 KB Output is correct
9 Correct 7 ms 9856 KB Output is correct
10 Correct 121 ms 20828 KB Output is correct
11 Correct 181 ms 24848 KB Output is correct
12 Correct 230 ms 25008 KB Output is correct
13 Correct 215 ms 25948 KB Output is correct
14 Correct 182 ms 25564 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 7 ms 9856 KB Output is correct
19 Correct 8 ms 9856 KB Output is correct
20 Incorrect 7 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 7 ms 9856 KB Output is correct
5 Correct 7 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 7 ms 9856 KB Output is correct
9 Correct 121 ms 20828 KB Output is correct
10 Correct 181 ms 24848 KB Output is correct
11 Correct 230 ms 25008 KB Output is correct
12 Correct 215 ms 25948 KB Output is correct
13 Correct 182 ms 25564 KB Output is correct
14 Execution timed out 2083 ms 23024 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 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 8 ms 9856 KB Output is correct
9 Correct 7 ms 9856 KB Output is correct
10 Correct 121 ms 20828 KB Output is correct
11 Correct 181 ms 24848 KB Output is correct
12 Correct 230 ms 25008 KB Output is correct
13 Correct 215 ms 25948 KB Output is correct
14 Correct 182 ms 25564 KB Output is correct
15 Execution timed out 2083 ms 23024 KB Time limit exceeded
16 Halted 0 ms 0 KB -