oj.uz

Submission #401949

# Submission time Handle Problem Language Result Execution time Memory
401949 2021-05-11T03:44:41 Z Blobo2_Blobo2 Swapping Cities (APIO20_swap) C++14
0 / 100
 2000 ms 16292 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;
                idx++;
                return;
            }
        }
    }
    return;
}
int dfs3(int u,int des,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,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++;
    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,y);
    return (max(cost,path2)==(int)1e9+5?-1:max(cost,path2));
}

Subtask #1
0 / 6.0

# Verdict Execution time Memory 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 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 60 ms 12044 KB Output is correct
10 Correct 106 ms 15880 KB Output is correct
11 Correct 138 ms 15620 KB Output is correct
12 Correct 135 ms 16292 KB Output is correct
13 Correct 158 ms 15848 KB Output is correct
14 Execution timed out 2080 ms 14756 KB Time limit exceeded
15 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4940 KB Output is correct
2 Correct 3 ms 4940 KB Output is correct
3 Execution timed out 2081 ms 12412 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
0 / 17.0

# Verdict Execution time Memory 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 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

# Verdict Execution time Memory 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 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 60 ms 12044 KB Output is correct
11 Correct 106 ms 15880 KB Output is correct
12 Correct 138 ms 15620 KB Output is correct
13 Correct 135 ms 16292 KB Output is correct
14 Correct 158 ms 15848 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

# Verdict Execution time Memory 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 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 60 ms 12044 KB Output is correct
10 Correct 106 ms 15880 KB Output is correct
11 Correct 138 ms 15620 KB Output is correct
12 Correct 135 ms 16292 KB Output is correct
13 Correct 158 ms 15848 KB Output is correct
14 Execution timed out 2080 ms 14756 KB Time limit exceeded
15 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory 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 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 60 ms 12044 KB Output is correct
11 Correct 106 ms 15880 KB Output is correct
12 Correct 138 ms 15620 KB Output is correct
13 Correct 135 ms 16292 KB Output is correct
14 Correct 158 ms 15848 KB Output is correct
15 Execution timed out 2080 ms 14756 KB Time limit exceeded
16 Halted 0 ms 0 KB -