oj.uz

답안 #394626

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
394626 2021-04-27T06:15:25 Z khangal 자매 도시 (APIO20_swap) C++14
0 / 100
 1 ms 332 KB 
#include "swap.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double db;
typedef pair<ll,ll> pl;
typedef vector<ll> vl;
#define pb push_back
#define po pop_back
#define ff first
#define ss second
#define MIN -1e18
#define MAX 1e18
#define lw lower_bound
// 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,c[1234567],x,y,z,l,r,cnt,cnt1,ans;
map<ll,ll> mp;
vector<pair<ll,pl>> edge;
ll firstnum,secondnum;
bool ok,ok1;
ll par[1234567],path[1234567],sz[1234567],w,mx[1234567];
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]}});
    }
    n=N;
    sort(edge.begin(),edge.end());
}

ll dsu(ll x){
    if(par[x]==x)return x;
    else return dsu(par[x]);
}

void connect(ll x,ll y){
    x=dsu(x);
    y=dsu(y);
    if(x!=y){
        par[y]=x;
        mx[x]=	max(mx[x],mx[y]);
        sz[x]+=sz[y];
        path[x]+=path[y];
    }
}

bool check(ll x,ll y){
	if(dsu(x)!=dsu(y))return false;
	return true;
}
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;
	}
}
int getMinimumFuelCapacity(int X, int Y) {
	run();
    for(auto u:edge){
        w=u.ff;
        x=u.ss.ff;
        y=u.ss.ss;
        connect(x,y);
        c[x]++;
        c[y]++;
        x=dsu(x);
        y=dsu(y);
        path[x]++;
        mx[x] = max(mx[x],c[x]);
        mx[y] = max(mx[y],c[y]);
        if(check(X,Y)==false)continue;
        if(mx[dsu(X)]>=3||path[dsu(X)]>=sz[dsu(X)])return w;
    }
}

Compilation message

swap.cpp: In function 'int getMinimumFuelCapacity(int, int)':
swap.cpp:81:1: warning: control reaches end of non-void function [-Wreturn-type]
   81 | }
      | ^

Subtask #1
0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 332 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 332 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 332 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 332 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 332 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 332 KB Output isn't correct
2 Halted 0 ms 0 KB -