oj.uz

Submission #412261

# Submission time Handle Problem Language Result Execution time Memory
412261 2021-05-26T16:12:11 Z Carmel_Ab1 Swapping Cities (APIO20_swap) C++17
0 / 100
 2000 ms 524292 KB 
#include<bits/stdc++.h>
#include "swap.h"

//#include "grader.cpp"

using namespace std;

typedef long double ld;
typedef long long ll;
typedef unsigned long long ull;
typedef vector<int>vi;
typedef vector<vector<int>>vvi;
typedef vector<ll>vl;
typedef vector<vl> vvl;
typedef pair<int,int>pi;
typedef pair<ll,ll> pl;
typedef vector<pl> vpl;
typedef vector<ld> vld;
typedef pair<ld,ld> pld;
//typedef tree<ll, null_type, less_equal<ll>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;
template<typename T> ostream& operator<<(ostream& os, vector<T>& a){os<<"[";for(int i=0; i<ll(a.size()); i++){os << a[i] << ((i!=ll(a.size()-1)?" ":""));}os << "]\n"; return os;}

#define all(x) x.begin(),x.end()
#define YES out("YES")
#define NO out("NO")
#define out(x){cout << x << "\n"; return;}
#define GLHF ios_base::sync_with_stdio(false); cin.tie(NULL)
#define print(x){for(auto ait:x) cout << ait << " "; cout << "\n";}
#define pb push_back
#define umap unordered_map


vector<vector<pi>> g;
vector<bool>vis;
int mx=-1;
void init(int n, int M,vi U,vi V,vi W){
    g.resize(n);
    vis.resize(n);
    mx=*max_element(all(W))+1;
    for(int i=0; i<M; i++){
        g[U[i]].pb({V[i],W[i]});
        g[V[i]].pb({U[i],W[i]});
    }
}

bool ans;
void dfs(int src,int par,int w){
    vis[src]=1;
    int cnt=0;
    
    for(pi nbr:g[src]) {
        if(nbr.first==par || nbr.second>w)continue;
        if(vis[nbr.first])ans=1;
        if(nbr.second<=w)cnt++;
        if(cnt>2)ans=1;
        else dfs(nbr.first,src,w);
    }
}
bool ok(int x,int y,int w){
    int n=g.size();
    for(int i=0; i<n; i++)
        vis[i]=0;
    ans=0;
    dfs(x,-1,w);
    if(!vis[y])return 0;
    return ans;

}

int getMinimumFuelCapacity(int X, int Y){
    ll l=1,r=mx,ans=-1;
    if(!ok(X,Y,mx))
        return -1;
    while(l<=r){
        ll m=(l+r)/2;
        if(ok(X,Y,m))
            ans=m,r=m-1;
        else
            l=m+1;
    }
    return ans;
}

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 2 ms 332 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 59 ms 11560 KB Output is correct
10 Correct 93 ms 13272 KB Output is correct
11 Correct 123 ms 13524 KB Output is correct
12 Correct 138 ms 13508 KB Output is correct
13 Correct 126 ms 14252 KB Output is correct
14 Execution timed out 2092 ms 11836 KB Time limit exceeded
15 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

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

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 2 ms 332 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Runtime error 323 ms 524292 KB Execution killed with signal 9

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 323 ms 524292 KB Execution killed with signal 9

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 2 ms 332 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 59 ms 11560 KB Output is correct
10 Correct 93 ms 13272 KB Output is correct
11 Correct 123 ms 13524 KB Output is correct
12 Correct 138 ms 13508 KB Output is correct
13 Correct 126 ms 14252 KB Output is correct
14 Execution timed out 2092 ms 11836 KB Time limit exceeded
15 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Runtime error 323 ms 524292 KB Execution killed with signal 9