oj.uz

답안 #292531

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
292531 2020-09-07T08:46:55 Z daniel920712 자매 도시 (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 all[200005];
bool use[200005];
bool use2[200005];
bool have2[200005];
bool have3[200005];
int Father[200005];
int y;
int ans=0;
int how=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)
{
    if(here==y)
    {
        //printf("%d\n",here);
        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))
        {
            //printf("%d\n",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;
    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) printf("%d %d\n",i,j.first.second);
            con++;

            if((i!=x&&i!=y&&con>=1)||con>=2)
            {
                //printf("%d %d\n",i,j.first.second);
                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]||use[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]||use[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;
    //printf("%d %d\n",t,ans);
    return max(t,ans);
    //return 0;
}

Subtask #1
0 / 6.0

# 결과 실행 시간 메모리 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 7 ms 9856 KB Output is correct
9 Correct 128 ms 20444 KB Output is correct
10 Correct 196 ms 24460 KB Output is correct
11 Correct 230 ms 24728 KB Output is correct
12 Correct 229 ms 25696 KB Output is correct
13 Correct 193 ms 25308 KB Output is correct
14 Execution timed out 2082 ms 22844 KB Time limit exceeded
15 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 9728 KB Output is correct
2 Correct 6 ms 9728 KB Output is correct
3 Execution timed out 2080 ms 23468 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 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 6 ms 9728 KB Output is correct
6 Correct 7 ms 9856 KB Output is correct
7 Correct 7 ms 9856 KB Output is correct
8 Correct 7 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 8 ms 9856 KB Output is correct
13 Correct 7 ms 9856 KB Output is correct
14 Correct 9 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

# 결과 실행 시간 메모리 Grader output
1 Correct 7 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 6 ms 9728 KB Output is correct
6 Correct 7 ms 9856 KB Output is correct
7 Correct 7 ms 9856 KB Output is correct
8 Correct 7 ms 9856 KB Output is correct
9 Correct 7 ms 9856 KB Output is correct
10 Correct 128 ms 20444 KB Output is correct
11 Correct 196 ms 24460 KB Output is correct
12 Correct 230 ms 24728 KB Output is correct
13 Correct 229 ms 25696 KB Output is correct
14 Correct 193 ms 25308 KB Output is correct
15 Correct 7 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 9 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

# 결과 실행 시간 메모리 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 7 ms 9856 KB Output is correct
9 Correct 128 ms 20444 KB Output is correct
10 Correct 196 ms 24460 KB Output is correct
11 Correct 230 ms 24728 KB Output is correct
12 Correct 229 ms 25696 KB Output is correct
13 Correct 193 ms 25308 KB Output is correct
14 Execution timed out 2082 ms 22844 KB Time limit exceeded
15 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 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 6 ms 9728 KB Output is correct
6 Correct 7 ms 9856 KB Output is correct
7 Correct 7 ms 9856 KB Output is correct
8 Correct 7 ms 9856 KB Output is correct
9 Correct 7 ms 9856 KB Output is correct
10 Correct 128 ms 20444 KB Output is correct
11 Correct 196 ms 24460 KB Output is correct
12 Correct 230 ms 24728 KB Output is correct
13 Correct 229 ms 25696 KB Output is correct
14 Correct 193 ms 25308 KB Output is correct
15 Execution timed out 2082 ms 22844 KB Time limit exceeded
16 Halted 0 ms 0 KB -