oj.uz

답안 #401959

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
401959 2021-05-11T04:18:46 Z Blobo2_Blobo2 자매 도시 (APIO20_swap) C++14
0 / 100
 2000 ms 16256 KB 
#include "swap.h"
//#include "grader.cpp"
#include <bits/stdc++.h>
#pragma GCC optimize ("O3")
#pragma GCC optimize ("unroll-loops")
using namespace std;
int n,m;
vector<pair<int,int> >adj[200001];
bool vis1[200001];
int mp[200001];
bool ok=0;
int idx=1;
void init(int N, int M, vector<int> U, vector<int> V, vector<int> W) {
    n=N,m=M;
    for(int i=0;i<M;i++){
        int x=U[i],y=V[i],c=W[i];
        adj[x].push_back({y,c});
        adj[y].push_back({x,c});
    }
}
int dfs1(int u,int des){
    if(u==des)
        return 0;
    vis1[u]=1;
    int ret=1e9+5;
    for(auto v:adj[u])
        if(!vis1[v.first])
            ret=min(ret,max(v.second,dfs1(v.first,des)));
    return ret;
}
int cost=-1;
void dfs2(int u,int des,int c=0){
    if(u==des){
        if(cost==c)
            ok=1;
        return;
    }
    vis1[u]=1;
    for(auto v:adj[u]){
        if(!vis1[v.first]){
            dfs2(v.first,des,max(c,v.second));
            if(ok){
                mp[v.first]=idx+1;
                idx++;
                return;
            }
        }
    }
    return;
}
int dfs3(int u,int des,int i=2){
    if(u==des)
        return 0;
    vis1[u]=1;
    int ret=1e9+5;
    for(auto v:adj[u]){
        if(!vis1[v.first]&&mp[v.first]!=i){
            if(mp[v.first]==i-1&&mp[u]==i);
            else{
                int c=max(v.second,dfs3(v.first,des,i+1));
                ret=min(ret,c);
            }
        }
    }
    return ret;
}

int getMinimumFuelCapacity(int x, int y) {
    ok=0;
    idx=1;
    cost=-1;
    for(int i=0;i<n;i++)vis1[i]=0,mp[i]=0;
    cost=dfs1(x,y);
    for(int i=0;i<n;i++)vis1[i]=0;
    dfs2(x,y);
    int mx=0;
    for(int i=0;i<n;i++)
        mx=max(mx,mp[i]);
    mx+=2;
    for(int i=0;i<n;i++){
        if(!mp[i])continue;
        mp[i]=mx-mp[i];
    }
    mp[x]=1;
    for(int i=0;i<n;i++)vis1[i]=0;
    int path2=dfs3(y,x);
    return (max(cost,path2)==(int)1e9+5?-1:max(cost,path2));
}

Subtask #1
0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 4940 KB Output is correct
2 Correct 3 ms 4940 KB Output is correct
3 Correct 3 ms 4940 KB Output is correct
4 Correct 3 ms 4940 KB Output is correct
5 Correct 4 ms 5100 KB Output is correct
6 Correct 4 ms 5068 KB Output is correct
7 Correct 4 ms 5068 KB Output is correct
8 Correct 4 ms 5068 KB Output is correct
9 Correct 66 ms 12940 KB Output is correct
10 Correct 108 ms 15168 KB Output is correct
11 Correct 135 ms 15628 KB Output is correct
12 Correct 141 ms 16256 KB Output is correct
13 Correct 161 ms 16224 KB Output is correct
14 Execution timed out 2078 ms 16044 KB Time limit exceeded
15 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

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

Subtask #3
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 4940 KB Output is correct
2 Correct 3 ms 4940 KB Output is correct
3 Correct 3 ms 4940 KB Output is correct
4 Correct 3 ms 4940 KB Output is correct
5 Correct 4 ms 5100 KB Output is correct
6 Correct 4 ms 5068 KB Output is correct
7 Correct 4 ms 5068 KB Output is correct
8 Correct 4 ms 5068 KB Output is correct
9 Correct 3 ms 4940 KB Output is correct
10 Incorrect 4 ms 4940 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 4940 KB Output is correct
2 Correct 4 ms 4940 KB Output is correct
3 Correct 3 ms 4940 KB Output is correct
4 Correct 3 ms 4940 KB Output is correct
5 Correct 3 ms 4940 KB Output is correct
6 Correct 4 ms 5100 KB Output is correct
7 Correct 4 ms 5068 KB Output is correct
8 Correct 4 ms 5068 KB Output is correct
9 Correct 4 ms 5068 KB Output is correct
10 Correct 66 ms 12940 KB Output is correct
11 Correct 108 ms 15168 KB Output is correct
12 Correct 135 ms 15628 KB Output is correct
13 Correct 141 ms 16256 KB Output is correct
14 Correct 161 ms 16224 KB Output is correct
15 Incorrect 4 ms 4940 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 4940 KB Output is correct
2 Correct 3 ms 4940 KB Output is correct
3 Correct 3 ms 4940 KB Output is correct
4 Correct 3 ms 4940 KB Output is correct
5 Correct 4 ms 5100 KB Output is correct
6 Correct 4 ms 5068 KB Output is correct
7 Correct 4 ms 5068 KB Output is correct
8 Correct 4 ms 5068 KB Output is correct
9 Correct 66 ms 12940 KB Output is correct
10 Correct 108 ms 15168 KB Output is correct
11 Correct 135 ms 15628 KB Output is correct
12 Correct 141 ms 16256 KB Output is correct
13 Correct 161 ms 16224 KB Output is correct
14 Execution timed out 2078 ms 16044 KB Time limit exceeded
15 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 4940 KB Output is correct
2 Correct 4 ms 4940 KB Output is correct
3 Correct 3 ms 4940 KB Output is correct
4 Correct 3 ms 4940 KB Output is correct
5 Correct 3 ms 4940 KB Output is correct
6 Correct 4 ms 5100 KB Output is correct
7 Correct 4 ms 5068 KB Output is correct
8 Correct 4 ms 5068 KB Output is correct
9 Correct 4 ms 5068 KB Output is correct
10 Correct 66 ms 12940 KB Output is correct
11 Correct 108 ms 15168 KB Output is correct
12 Correct 135 ms 15628 KB Output is correct
13 Correct 141 ms 16256 KB Output is correct
14 Correct 161 ms 16224 KB Output is correct
15 Execution timed out 2078 ms 16044 KB Time limit exceeded
16 Halted 0 ms 0 KB -