oj.uz

Submission #412301

# Submission time Handle Problem Language Result Execution time Memory
412301 2021-05-26T16:54:56 Z Carmel_Ab1 Swapping Cities (APIO20_swap) C++17
50 / 100
 2000 ms 27696 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


struct dsu{
    vi par,deg;
    vector<bool>is_line;

    dsu (int n){
        par.resize(n);
        for(int i=0; i<n; i++)
            par[i]=i;
        deg.resize(n);
        is_line.resize(n,1);
    }
    int get(int x){return par[x]=(x==par[x]?x:get(par[x]));}

    void unite(int u,int v){
        bool ok=(deg[u]+1)>2 || (deg[v]+1)>2 || get(u)==get(v);
        deg[u]++,deg[v]++;
        if(rand()%2)swap(u,v);
        if(ok)
            is_line[get(u)]=is_line[get(v)]=0;
        if(!is_line[get(u)] || !is_line[get(v)])
            is_line[get(u)]=is_line[get(v)]=0;

        u=get(u),v=get(v);
        par[u]=v;
    }

};
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;
    int n=g.size();
    dsu d(n);
    for(int i=0; i<E.size(); i++){
        d.unite(E[i][1],E[i][2]);
        if(d.get(X)==d.get(Y) && !d.is_line[d.get(X)])
            return E[i][0];
    }
    return -1;
}

Compilation message

swap.cpp: In function 'void init(int, int, vi, vi, vi)':
swap.cpp:81: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]
   81 |     star&=g[0].size()==n-1 && M==n-1;
      |           ~~~~~~~~~~~^~~~~
swap.cpp: In function 'int getMinimumFuelCapacity(int, int)':
swap.cpp:137:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  137 |     for(int i=0; i<E.size(); i++){
      |                  ~^~~~~~~~~
swap.cpp:134:8: warning: unused variable 'l' [-Wunused-variable]
  134 |     ll l=1,r=mx,ans=-1;
      |        ^
swap.cpp:134:12: warning: unused variable 'r' [-Wunused-variable]
  134 |     ll l=1,r=mx,ans=-1;
      |            ^
swap.cpp:134:17: warning: unused variable 'ans' [-Wunused-variable]
  134 |     ll l=1,r=mx,ans=-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 1 ms 332 KB Output is correct
7 Correct 2 ms 424 KB Output is correct
8 Correct 2 ms 424 KB Output is correct
9 Correct 83 ms 13140 KB Output is correct
10 Correct 98 ms 15028 KB Output is correct
11 Correct 128 ms 14836 KB Output is correct
12 Correct 129 ms 15712 KB Output is correct
13 Correct 94 ms 15712 KB Output is correct
14 Correct 118 ms 13416 KB Output is correct
15 Correct 164 ms 19384 KB Output is correct
16 Correct 153 ms 18868 KB Output is correct
17 Correct 165 ms 19816 KB Output is correct
18 Correct 159 ms 19836 KB Output is correct
19 Correct 69 ms 7832 KB Output is correct
20 Correct 172 ms 20284 KB Output is correct
21 Correct 161 ms 20140 KB Output is correct
22 Correct 169 ms 21120 KB Output is correct
23 Correct 180 ms 21188 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 20408 KB Output is correct
4 Correct 164 ms 21068 KB Output is correct
5 Correct 158 ms 20944 KB Output is correct
6 Correct 154 ms 20812 KB Output is correct
7 Correct 169 ms 21032 KB Output is correct
8 Correct 151 ms 20412 KB Output is correct
9 Correct 154 ms 20792 KB Output is correct
10 Correct 148 ms 20456 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 1 ms 332 KB Output is correct
7 Correct 2 ms 424 KB Output is correct
8 Correct 2 ms 424 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 2 ms 332 KB Output is correct
11 Correct 2 ms 428 KB Output is correct
12 Correct 2 ms 396 KB Output is correct
13 Correct 2 ms 332 KB Output is correct
14 Correct 2 ms 332 KB Output is correct
15 Correct 2 ms 428 KB Output is correct
16 Correct 2 ms 332 KB Output is correct
17 Correct 2 ms 332 KB Output is correct
18 Correct 2 ms 332 KB Output is correct
19 Correct 2 ms 432 KB Output is correct
20 Correct 2 ms 332 KB Output is correct
21 Correct 2 ms 460 KB Output is correct
22 Correct 2 ms 460 KB Output is correct
23 Correct 2 ms 332 KB Output is correct
24 Correct 2 ms 460 KB Output is correct
25 Correct 3 ms 452 KB Output is correct
26 Correct 2 ms 460 KB Output is correct
27 Correct 2 ms 428 KB Output is correct
28 Correct 2 ms 556 KB Output is correct

Subtask #4
20.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 1 ms 332 KB Output is correct
8 Correct 2 ms 424 KB Output is correct
9 Correct 2 ms 424 KB Output is correct
10 Correct 83 ms 13140 KB Output is correct
11 Correct 98 ms 15028 KB Output is correct
12 Correct 128 ms 14836 KB Output is correct
13 Correct 129 ms 15712 KB Output is correct
14 Correct 94 ms 15712 KB Output is correct
15 Correct 2 ms 332 KB Output is correct
16 Correct 2 ms 428 KB Output is correct
17 Correct 2 ms 396 KB Output is correct
18 Correct 2 ms 332 KB Output is correct
19 Correct 2 ms 332 KB Output is correct
20 Correct 2 ms 428 KB Output is correct
21 Correct 2 ms 332 KB Output is correct
22 Correct 2 ms 332 KB Output is correct
23 Correct 2 ms 332 KB Output is correct
24 Correct 2 ms 432 KB Output is correct
25 Correct 2 ms 332 KB Output is correct
26 Correct 2 ms 460 KB Output is correct
27 Correct 2 ms 460 KB Output is correct
28 Correct 2 ms 332 KB Output is correct
29 Correct 2 ms 460 KB Output is correct
30 Correct 3 ms 452 KB Output is correct
31 Correct 2 ms 460 KB Output is correct
32 Correct 2 ms 428 KB Output is correct
33 Correct 2 ms 556 KB Output is correct
34 Correct 16 ms 2440 KB Output is correct
35 Correct 153 ms 15372 KB Output is correct
36 Correct 158 ms 15368 KB Output is correct
37 Correct 177 ms 15348 KB Output is correct
38 Correct 151 ms 15220 KB Output is correct
39 Correct 150 ms 15200 KB Output is correct
40 Correct 143 ms 14060 KB Output is correct
41 Correct 149 ms 15712 KB Output is correct
42 Correct 150 ms 15324 KB Output is correct
43 Correct 160 ms 15320 KB Output is correct
44 Correct 168 ms 16100 KB Output is correct
45 Correct 209 ms 22788 KB Output is correct
46 Correct 154 ms 15312 KB Output is correct
47 Correct 167 ms 15456 KB Output is correct
48 Correct 157 ms 16736 KB Output is correct
49 Correct 116 ms 20200 KB Output is correct
50 Correct 115 ms 15308 KB Output is correct
51 Correct 149 ms 18100 KB Output is correct
52 Correct 227 ms 24112 KB Output is correct
53 Correct 265 ms 25448 KB Output is correct
54 Correct 289 ms 27696 KB Output is correct
55 Correct 131 ms 15444 KB Output is correct
56 Correct 269 ms 24612 KB Output is correct

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 424 KB Output is correct
8 Correct 2 ms 424 KB Output is correct
9 Correct 83 ms 13140 KB Output is correct
10 Correct 98 ms 15028 KB Output is correct
11 Correct 128 ms 14836 KB Output is correct
12 Correct 129 ms 15712 KB Output is correct
13 Correct 94 ms 15712 KB Output is correct
14 Correct 118 ms 13416 KB Output is correct
15 Correct 164 ms 19384 KB Output is correct
16 Correct 153 ms 18868 KB Output is correct
17 Correct 165 ms 19816 KB Output is correct
18 Correct 159 ms 19836 KB Output is correct
19 Correct 156 ms 20408 KB Output is correct
20 Correct 164 ms 21068 KB Output is correct
21 Correct 158 ms 20944 KB Output is correct
22 Correct 154 ms 20812 KB Output is correct
23 Correct 169 ms 21032 KB Output is correct
24 Correct 151 ms 20412 KB Output is correct
25 Correct 154 ms 20792 KB Output is correct
26 Correct 148 ms 20456 KB Output is correct
27 Correct 2 ms 332 KB Output is correct
28 Correct 2 ms 428 KB Output is correct
29 Correct 2 ms 396 KB Output is correct
30 Correct 2 ms 332 KB Output is correct
31 Correct 2 ms 332 KB Output is correct
32 Correct 2 ms 428 KB Output is correct
33 Correct 2 ms 332 KB Output is correct
34 Correct 2 ms 332 KB Output is correct
35 Correct 2 ms 332 KB Output is correct
36 Correct 16 ms 2440 KB Output is correct
37 Correct 153 ms 15372 KB Output is correct
38 Correct 158 ms 15368 KB Output is correct
39 Correct 177 ms 15348 KB Output is correct
40 Correct 151 ms 15220 KB Output is correct
41 Correct 150 ms 15200 KB Output is correct
42 Correct 143 ms 14060 KB Output is correct
43 Correct 149 ms 15712 KB Output is correct
44 Correct 150 ms 15324 KB Output is correct
45 Correct 160 ms 15320 KB Output is correct
46 Correct 168 ms 16100 KB Output is correct
47 Execution timed out 2076 ms 2532 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 1 ms 332 KB Output is correct
8 Correct 2 ms 424 KB Output is correct
9 Correct 2 ms 424 KB Output is correct
10 Correct 83 ms 13140 KB Output is correct
11 Correct 98 ms 15028 KB Output is correct
12 Correct 128 ms 14836 KB Output is correct
13 Correct 129 ms 15712 KB Output is correct
14 Correct 94 ms 15712 KB Output is correct
15 Correct 118 ms 13416 KB Output is correct
16 Correct 164 ms 19384 KB Output is correct
17 Correct 153 ms 18868 KB Output is correct
18 Correct 165 ms 19816 KB Output is correct
19 Correct 159 ms 19836 KB Output is correct
20 Correct 156 ms 20408 KB Output is correct
21 Correct 164 ms 21068 KB Output is correct
22 Correct 158 ms 20944 KB Output is correct
23 Correct 154 ms 20812 KB Output is correct
24 Correct 169 ms 21032 KB Output is correct
25 Correct 151 ms 20412 KB Output is correct
26 Correct 154 ms 20792 KB Output is correct
27 Correct 148 ms 20456 KB Output is correct
28 Correct 2 ms 332 KB Output is correct
29 Correct 2 ms 428 KB Output is correct
30 Correct 2 ms 396 KB Output is correct
31 Correct 2 ms 332 KB Output is correct
32 Correct 2 ms 332 KB Output is correct
33 Correct 2 ms 428 KB Output is correct
34 Correct 2 ms 332 KB Output is correct
35 Correct 2 ms 332 KB Output is correct
36 Correct 2 ms 332 KB Output is correct
37 Correct 16 ms 2440 KB Output is correct
38 Correct 153 ms 15372 KB Output is correct
39 Correct 158 ms 15368 KB Output is correct
40 Correct 177 ms 15348 KB Output is correct
41 Correct 151 ms 15220 KB Output is correct
42 Correct 150 ms 15200 KB Output is correct
43 Correct 143 ms 14060 KB Output is correct
44 Correct 149 ms 15712 KB Output is correct
45 Correct 150 ms 15324 KB Output is correct
46 Correct 160 ms 15320 KB Output is correct
47 Correct 168 ms 16100 KB Output is correct
48 Execution timed out 2076 ms 2532 KB Time limit exceeded
49 Halted 0 ms 0 KB -