oj.uz

Submission #394746

# Submission time Handle Problem Language Result Execution time Memory
394746 2021-04-27T09:12:11 Z khangal Swapping Cities (APIO20_swap) C++14
6 / 100
 128 ms 9252 KB 
#include "swap.h"
#include<bits/stdc++.h>
using namespace std;
typedef int ll;
typedef pair<ll,ll> pl;
#define pb push_back
#define ff first
#define ss second
// typedef tree<ll , null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update> indexed_set;
// template< typename T>
// using indexed_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
ll n,m,mid,mn,T,sum,h1,h2,x,y,z,l,r,cnt,cnt1,ans;
vector<pair<ll,pl>> edge;
bool ok,ok1;
vector<int> par,path,sz,w,mx,lvl,c;
ll len;
void init(int N, int M,
          std::vector<int> U, std::vector<int> V, std::vector<int> W) {
    for(int i=0;i<M;i++){
        edge.pb({W[i],{U[i],V[i]}});
        ans=max(ans,W[i]);
    }
    n=N;
    m=M;
    par.resize(n);
	path.resize(n);
    sz.resize(n);
    mx.resize(n);
    lvl.resize(n);
    c.resize(n);
    sort(edge.begin(),edge.end());
    len=U.size();
}


int dsu(ll x){
    return par[x] = (par[x] == x ? x : dsu(par[x]));
}
 
void connect(ll x,ll y){
    x=dsu(x);
    y=dsu(y);
    if(x==y){
    	return;
    }
    else{
    	
    	if(lvl[x]>=lvl[y]){
	        par[y]=x;
	        mx[x]=max(mx[x],mx[y]);
	        sz[x]+=sz[y];
	        path[x]+=path[y];
		}
		else{
			par[x]=y;
	        mx[y]=max(mx[x],mx[y]);
	        sz[y]+=sz[x];
	        path[y]+=path[x];
		}
	}
}

void run(){
	for(int i=0;i<n;i++){
        par[i]=i;
    }
    for(int i=0;i<n;i++){
    	c[i]=0;
    	path[i]=0;
    	sz[i]=1;
    	mx[i]=0;
    	lvl[i]=0;
	}
}
int getMinimumFuelCapacity(int X, int Y) {
	if(len<=5){
	run();
    for(auto u:edge){
        x=u.ss.ff;
        y=u.ss.ss;
        connect(x,y);
        c[x]++;
        c[y]++;
        path[dsu(x)]++;
        mx[dsu(x)] = max(mx[dsu(x)],c[x]);
        mx[dsu(y)] = max(mx[dsu(y)],c[y]);
        if(dsu(X)!=dsu(Y))continue;
        if(mx[dsu(X)]<3&&path[dsu(X)]<sz[dsu(X)])continue;
        return u.ff;
    }
    return -1;}
    else{
		if(m+1==n)return -1;
		else return ans;
	}
}

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 1 ms 208 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 1 ms 332 KB Output is correct
9 Correct 37 ms 4788 KB Output is correct
10 Correct 51 ms 5944 KB Output is correct
11 Correct 43 ms 5880 KB Output is correct
12 Correct 46 ms 6080 KB Output is correct
13 Correct 45 ms 6072 KB Output is correct
14 Correct 42 ms 4920 KB Output is correct
15 Correct 107 ms 7708 KB Output is correct
16 Correct 128 ms 7700 KB Output is correct
17 Correct 111 ms 7828 KB Output is correct
18 Correct 115 ms 7860 KB Output is correct
19 Correct 78 ms 4620 KB Output is correct
20 Correct 109 ms 8900 KB Output is correct
21 Correct 110 ms 8932 KB Output is correct
22 Correct 123 ms 9252 KB Output is correct
23 Correct 113 ms 9244 KB Output is correct

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Incorrect 106 ms 7452 KB Output isn't correct
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 0 ms 204 KB Output is correct
3 Correct 1 ms 208 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 1 ms 332 KB Output is correct
9 Incorrect 1 ms 204 KB Output isn't correct

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 204 KB Output isn't correct

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 1 ms 208 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 1 ms 332 KB Output is correct
9 Correct 37 ms 4788 KB Output is correct
10 Correct 51 ms 5944 KB Output is correct
11 Correct 43 ms 5880 KB Output is correct
12 Correct 46 ms 6080 KB Output is correct
13 Correct 45 ms 6072 KB Output is correct
14 Correct 42 ms 4920 KB Output is correct
15 Correct 107 ms 7708 KB Output is correct
16 Correct 128 ms 7700 KB Output is correct
17 Correct 111 ms 7828 KB Output is correct
18 Correct 115 ms 7860 KB Output is correct
19 Incorrect 106 ms 7452 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 204 KB Output isn't correct