oj.uz

Submission #401950

# Submission time Handle Problem Language Result Execution time Memory
401950 2021-05-11T03:48:31 Z Blobo2_Blobo2 Swapping Cities (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

# 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 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

# 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 2092 ms 12508 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 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

# 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 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

# 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 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

# 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 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 -