oj.uz

Submission #412279

# Submission time Handle Problem Language Result Execution time Memory
412279 2021-05-26T16:33:52 Z Carmel_Ab1 Swapping Cities (APIO20_swap) C++17
30 / 100
 2000 ms 25808 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;

bool cyc=1,line=1,star=1;
vvi E;

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]});
        E.pb({W[i],min(U[i],V[i]),max(U[i],V[i])});
    }
    sort(all(E));
    for(int i=0; i<n; i++)
        cyc&=g[i].size()==2,line&=g[i].size()<=2;
    line&=!cyc;
    star&=g[0].size()==n-1 && M==n-1;
}

bool ans;
void dfs(int src,int par,int w){
    vis[src]=1;
    int cnt=0;
    for(pi nbr:g[src])
        if(nbr.second<=w)
            cnt++;
    if(cnt>2)
        ans=1;
    for(pi nbr:g[src]) {
        if(nbr.first==par || nbr.second>w)continue;
        if(vis[nbr.first])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]=false;
    ans=0;
    dfs(x,-1,w);
    if(!vis[y])return 0;
    return ans;

}
int starr(int X,int Y){
    if(X>Y)swap(X,Y);
    int n=g.size();
    if(n<=3)return -1;

    if(X==0){
        if(E[0][2]==Y || E[1][2]==Y)
            return E[2][0];
        else return g[Y][0].second;
    }
    else{
        if(E[0][2]==X && E[1][2]==Y)
            return E[2][0];
        else if(E[0][2]==Y && E[1][2]==X)
            return E[2][0];
        else
            return max(g[X][0].second,g[Y][0].second);
    }
}

int getMinimumFuelCapacity(int X, int Y){
    if(line)return -1;
    else if(cyc)return mx-1;
    else if(star)return starr(X,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;
}

Compilation message

swap.cpp: In function 'void init(int, int, vi, vi, vi)':
swap.cpp:54:22: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   54 |     star&=g[0].size()==n-1 && M==n-1;
      |           ~~~~~~~~~~~^~~~~

Subtask #1
6.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 2 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 69 ms 11516 KB Output is correct
10 Correct 93 ms 13088 KB Output is correct
11 Correct 90 ms 12884 KB Output is correct
12 Correct 96 ms 13552 KB Output is correct
13 Correct 100 ms 13612 KB Output is correct
14 Correct 81 ms 11612 KB Output is correct
15 Correct 179 ms 14944 KB Output is correct
16 Correct 209 ms 14624 KB Output is correct
17 Correct 151 ms 15320 KB Output is correct
18 Correct 156 ms 15320 KB Output is correct
19 Correct 68 ms 5808 KB Output is correct
20 Correct 158 ms 16256 KB Output is correct
21 Correct 149 ms 15848 KB Output is correct
22 Correct 159 ms 16872 KB Output is correct
23 Correct 169 ms 16852 KB Output is correct

Subtask #2
7.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 Correct 156 ms 16652 KB Output is correct
4 Correct 163 ms 17224 KB Output is correct
5 Correct 179 ms 16976 KB Output is correct
6 Correct 157 ms 17096 KB Output is correct
7 Correct 173 ms 17104 KB Output is correct
8 Correct 156 ms 16548 KB Output is correct
9 Correct 159 ms 16996 KB Output is correct
10 Correct 159 ms 16420 KB Output is correct

Subtask #3
17.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 2 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 1 ms 204 KB Output is correct
10 Correct 3 ms 332 KB Output is correct
11 Correct 3 ms 460 KB Output is correct
12 Correct 3 ms 332 KB Output is correct
13 Correct 3 ms 332 KB Output is correct
14 Correct 3 ms 332 KB Output is correct
15 Correct 3 ms 332 KB Output is correct
16 Correct 3 ms 460 KB Output is correct
17 Correct 3 ms 460 KB Output is correct
18 Correct 4 ms 332 KB Output is correct
19 Correct 3 ms 332 KB Output is correct
20 Correct 3 ms 460 KB Output is correct
21 Correct 4 ms 548 KB Output is correct
22 Correct 4 ms 460 KB Output is correct
23 Correct 3 ms 332 KB Output is correct
24 Correct 5 ms 460 KB Output is correct
25 Correct 5 ms 460 KB Output is correct
26 Correct 8 ms 460 KB Output is correct
27 Correct 3 ms 460 KB Output is correct
28 Correct 6 ms 460 KB Output is correct

Subtask #4
0 / 20.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 204 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 2 ms 332 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 69 ms 11516 KB Output is correct
11 Correct 93 ms 13088 KB Output is correct
12 Correct 90 ms 12884 KB Output is correct
13 Correct 96 ms 13552 KB Output is correct
14 Correct 100 ms 13612 KB Output is correct
15 Correct 3 ms 332 KB Output is correct
16 Correct 3 ms 460 KB Output is correct
17 Correct 3 ms 332 KB Output is correct
18 Correct 3 ms 332 KB Output is correct
19 Correct 3 ms 332 KB Output is correct
20 Correct 3 ms 332 KB Output is correct
21 Correct 3 ms 460 KB Output is correct
22 Correct 3 ms 460 KB Output is correct
23 Correct 4 ms 332 KB Output is correct
24 Correct 3 ms 332 KB Output is correct
25 Correct 3 ms 460 KB Output is correct
26 Correct 4 ms 548 KB Output is correct
27 Correct 4 ms 460 KB Output is correct
28 Correct 3 ms 332 KB Output is correct
29 Correct 5 ms 460 KB Output is correct
30 Correct 5 ms 460 KB Output is correct
31 Correct 8 ms 460 KB Output is correct
32 Correct 3 ms 460 KB Output is correct
33 Correct 6 ms 460 KB Output is correct
34 Correct 23 ms 2180 KB Output is correct
35 Correct 406 ms 17104 KB Output is correct
36 Correct 287 ms 15132 KB Output is correct
37 Correct 321 ms 13556 KB Output is correct
38 Correct 483 ms 13404 KB Output is correct
39 Correct 427 ms 13300 KB Output is correct
40 Correct 467 ms 12408 KB Output is correct
41 Correct 877 ms 15584 KB Output is correct
42 Correct 422 ms 16472 KB Output is correct
43 Correct 682 ms 18148 KB Output is correct
44 Correct 758 ms 14064 KB Output is correct
45 Correct 1251 ms 19604 KB Output is correct
46 Correct 573 ms 16720 KB Output is correct
47 Correct 652 ms 13516 KB Output is correct
48 Correct 789 ms 14664 KB Output is correct
49 Correct 214 ms 17392 KB Output is correct
50 Correct 244 ms 12992 KB Output is correct
51 Correct 763 ms 16468 KB Output is correct
52 Correct 1216 ms 22016 KB Output is correct
53 Correct 882 ms 22720 KB Output is correct
54 Execution timed out 2066 ms 25808 KB Time limit exceeded
55 Halted 0 ms 0 KB -

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 2 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 69 ms 11516 KB Output is correct
10 Correct 93 ms 13088 KB Output is correct
11 Correct 90 ms 12884 KB Output is correct
12 Correct 96 ms 13552 KB Output is correct
13 Correct 100 ms 13612 KB Output is correct
14 Correct 81 ms 11612 KB Output is correct
15 Correct 179 ms 14944 KB Output is correct
16 Correct 209 ms 14624 KB Output is correct
17 Correct 151 ms 15320 KB Output is correct
18 Correct 156 ms 15320 KB Output is correct
19 Correct 156 ms 16652 KB Output is correct
20 Correct 163 ms 17224 KB Output is correct
21 Correct 179 ms 16976 KB Output is correct
22 Correct 157 ms 17096 KB Output is correct
23 Correct 173 ms 17104 KB Output is correct
24 Correct 156 ms 16548 KB Output is correct
25 Correct 159 ms 16996 KB Output is correct
26 Correct 159 ms 16420 KB Output is correct
27 Correct 3 ms 332 KB Output is correct
28 Correct 3 ms 460 KB Output is correct
29 Correct 3 ms 332 KB Output is correct
30 Correct 3 ms 332 KB Output is correct
31 Correct 3 ms 332 KB Output is correct
32 Correct 3 ms 332 KB Output is correct
33 Correct 3 ms 460 KB Output is correct
34 Correct 3 ms 460 KB Output is correct
35 Correct 4 ms 332 KB Output is correct
36 Correct 23 ms 2180 KB Output is correct
37 Correct 406 ms 17104 KB Output is correct
38 Correct 287 ms 15132 KB Output is correct
39 Correct 321 ms 13556 KB Output is correct
40 Correct 483 ms 13404 KB Output is correct
41 Correct 427 ms 13300 KB Output is correct
42 Correct 467 ms 12408 KB Output is correct
43 Correct 877 ms 15584 KB Output is correct
44 Correct 422 ms 16472 KB Output is correct
45 Correct 682 ms 18148 KB Output is correct
46 Correct 758 ms 14064 KB Output is correct
47 Execution timed out 2092 ms 2624 KB Time limit exceeded
48 Halted 0 ms 0 KB -

Subtask #6
0 / 27.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 204 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 2 ms 332 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 69 ms 11516 KB Output is correct
11 Correct 93 ms 13088 KB Output is correct
12 Correct 90 ms 12884 KB Output is correct
13 Correct 96 ms 13552 KB Output is correct
14 Correct 100 ms 13612 KB Output is correct
15 Correct 81 ms 11612 KB Output is correct
16 Correct 179 ms 14944 KB Output is correct
17 Correct 209 ms 14624 KB Output is correct
18 Correct 151 ms 15320 KB Output is correct
19 Correct 156 ms 15320 KB Output is correct
20 Correct 156 ms 16652 KB Output is correct
21 Correct 163 ms 17224 KB Output is correct
22 Correct 179 ms 16976 KB Output is correct
23 Correct 157 ms 17096 KB Output is correct
24 Correct 173 ms 17104 KB Output is correct
25 Correct 156 ms 16548 KB Output is correct
26 Correct 159 ms 16996 KB Output is correct
27 Correct 159 ms 16420 KB Output is correct
28 Correct 3 ms 332 KB Output is correct
29 Correct 3 ms 460 KB Output is correct
30 Correct 3 ms 332 KB Output is correct
31 Correct 3 ms 332 KB Output is correct
32 Correct 3 ms 332 KB Output is correct
33 Correct 3 ms 332 KB Output is correct
34 Correct 3 ms 460 KB Output is correct
35 Correct 3 ms 460 KB Output is correct
36 Correct 4 ms 332 KB Output is correct
37 Correct 23 ms 2180 KB Output is correct
38 Correct 406 ms 17104 KB Output is correct
39 Correct 287 ms 15132 KB Output is correct
40 Correct 321 ms 13556 KB Output is correct
41 Correct 483 ms 13404 KB Output is correct
42 Correct 427 ms 13300 KB Output is correct
43 Correct 467 ms 12408 KB Output is correct
44 Correct 877 ms 15584 KB Output is correct
45 Correct 422 ms 16472 KB Output is correct
46 Correct 682 ms 18148 KB Output is correct
47 Correct 758 ms 14064 KB Output is correct
48 Execution timed out 2092 ms 2624 KB Time limit exceeded
49 Halted 0 ms 0 KB -