oj.uz

답안 #292499

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
292499 2020-09-07T06:47:45 Z daniel920712 자매 도시 (APIO20_swap) C++14
0 / 100
 2000 ms 25900 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]={0};

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))
        {
            have2[here]=1;
            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));
    }
}

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;
        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(auto i:Next[x])
    {
        if(use[i.second]) continue;
        for(j=0;j<NN;j++) use2[j]=0;
        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]) continue;
            if(have2[b])
            {
                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;
    return max(t,ans);
}

Subtask #1
0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 9728 KB Output is correct
2 Correct 7 ms 9728 KB Output is correct
3 Correct 7 ms 9856 KB Output is correct
4 Correct 7 ms 9856 KB Output is correct
5 Correct 9 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 118 ms 20700 KB Output is correct
10 Correct 190 ms 24848 KB Output is correct
11 Correct 230 ms 24984 KB Output is correct
12 Correct 212 ms 25900 KB Output is correct
13 Correct 184 ms 25436 KB Output is correct
14 Execution timed out 2089 ms 22960 KB Time limit exceeded
15 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 9728 KB Output is correct
2 Correct 7 ms 9728 KB Output is correct
3 Execution timed out 2088 ms 23692 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 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 9 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 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

# 결과 실행 시간 메모리 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 9 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 118 ms 20700 KB Output is correct
11 Correct 190 ms 24848 KB Output is correct
12 Correct 230 ms 24984 KB Output is correct
13 Correct 212 ms 25900 KB Output is correct
14 Correct 184 ms 25436 KB Output is correct
15 Correct 8 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

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 9728 KB Output is correct
2 Correct 7 ms 9728 KB Output is correct
3 Correct 7 ms 9856 KB Output is correct
4 Correct 7 ms 9856 KB Output is correct
5 Correct 9 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 118 ms 20700 KB Output is correct
10 Correct 190 ms 24848 KB Output is correct
11 Correct 230 ms 24984 KB Output is correct
12 Correct 212 ms 25900 KB Output is correct
13 Correct 184 ms 25436 KB Output is correct
14 Execution timed out 2089 ms 22960 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 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 9 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 118 ms 20700 KB Output is correct
11 Correct 190 ms 24848 KB Output is correct
12 Correct 230 ms 24984 KB Output is correct
13 Correct 212 ms 25900 KB Output is correct
14 Correct 184 ms 25436 KB Output is correct
15 Execution timed out 2089 ms 22960 KB Time limit exceeded
16 Halted 0 ms 0 KB -