oj.uz

답안 #401950

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
401950 2021-05-11T03:48:31 Z Blobo2_Blobo2 자매 도시 (APIO20_swap) C++14
0 / 100
 2000 ms 15872 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 des;
int dfs1(int u){
    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)));
    return ret;
}
int cost=-1;
void dfs2(int u,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,max(c,v.second));
            if(ok){
                mp[v.first]=idx;
                idx++;
                return;
            }
        }
    }
    return;
}
int dfs3(int u,int i=1){
    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){
            int c=max(v.second,dfs3(v.first,i+1));
            ret=min(ret,c);
        }
    }
    return ret;
}

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

Subtask #1
0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 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 5068 KB Output is correct
6 Correct 4 ms 5060 KB Output is correct
7 Correct 4 ms 5068 KB Output is correct
8 Correct 4 ms 5068 KB Output is correct
9 Correct 62 ms 12040 KB Output is correct
10 Correct 103 ms 15872 KB Output is correct
11 Correct 157 ms 15048 KB Output is correct
12 Correct 137 ms 14852 KB Output is correct
13 Correct 142 ms 15788 KB Output is correct
14 Execution timed out 2068 ms 14576 KB Time limit exceeded
15 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

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

Subtask #3
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 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 5068 KB Output is correct
6 Correct 4 ms 5060 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 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 3 ms 4940 KB Output is correct
6 Correct 4 ms 5068 KB Output is correct
7 Correct 4 ms 5060 KB Output is correct
8 Correct 4 ms 5068 KB Output is correct
9 Correct 4 ms 5068 KB Output is correct
10 Correct 62 ms 12040 KB Output is correct
11 Correct 103 ms 15872 KB Output is correct
12 Correct 157 ms 15048 KB Output is correct
13 Correct 137 ms 14852 KB Output is correct
14 Correct 142 ms 15788 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 3 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 5068 KB Output is correct
6 Correct 4 ms 5060 KB Output is correct
7 Correct 4 ms 5068 KB Output is correct
8 Correct 4 ms 5068 KB Output is correct
9 Correct 62 ms 12040 KB Output is correct
10 Correct 103 ms 15872 KB Output is correct
11 Correct 157 ms 15048 KB Output is correct
12 Correct 137 ms 14852 KB Output is correct
13 Correct 142 ms 15788 KB Output is correct
14 Execution timed out 2068 ms 14576 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 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 3 ms 4940 KB Output is correct
6 Correct 4 ms 5068 KB Output is correct
7 Correct 4 ms 5060 KB Output is correct
8 Correct 4 ms 5068 KB Output is correct
9 Correct 4 ms 5068 KB Output is correct
10 Correct 62 ms 12040 KB Output is correct
11 Correct 103 ms 15872 KB Output is correct
12 Correct 157 ms 15048 KB Output is correct
13 Correct 137 ms 14852 KB Output is correct
14 Correct 142 ms 15788 KB Output is correct
15 Execution timed out 2068 ms 14576 KB Time limit exceeded
16 Halted 0 ms 0 KB -