oj.uz

답안 #394628

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
394628 2021-04-27T06:17:21 Z khangal 자매 도시 (APIO20_swap) C++14
0 / 100
 2000 ms 11376 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;
    }
    return -1;
}

Subtask #1
0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 316 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 312 KB Output is correct
5 Correct 1 ms 460 KB Output is correct
6 Correct 2 ms 332 KB Output is correct
7 Correct 1 ms 460 KB Output is correct
8 Correct 2 ms 460 KB Output is correct
9 Correct 53 ms 7768 KB Output is correct
10 Correct 71 ms 9460 KB Output is correct
11 Correct 76 ms 9400 KB Output is correct
12 Correct 78 ms 9880 KB Output is correct
13 Execution timed out 2074 ms 9756 KB Time limit exceeded

Subtask #2
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 316 KB Output is correct
3 Execution timed out 2068 ms 11376 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 316 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 312 KB Output is correct
5 Correct 1 ms 460 KB Output is correct
6 Correct 2 ms 332 KB Output is correct
7 Correct 1 ms 460 KB Output is correct
8 Correct 2 ms 460 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 464 KB Output is correct
11 Incorrect 1 ms 460 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 316 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 312 KB Output is correct
6 Correct 1 ms 460 KB Output is correct
7 Correct 2 ms 332 KB Output is correct
8 Correct 1 ms 460 KB Output is correct
9 Correct 2 ms 460 KB Output is correct
10 Correct 53 ms 7768 KB Output is correct
11 Correct 71 ms 9460 KB Output is correct
12 Correct 76 ms 9400 KB Output is correct
13 Correct 78 ms 9880 KB Output is correct
14 Execution timed out 2074 ms 9756 KB Time limit exceeded

Subtask #5
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 316 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 312 KB Output is correct
5 Correct 1 ms 460 KB Output is correct
6 Correct 2 ms 332 KB Output is correct
7 Correct 1 ms 460 KB Output is correct
8 Correct 2 ms 460 KB Output is correct
9 Correct 53 ms 7768 KB Output is correct
10 Correct 71 ms 9460 KB Output is correct
11 Correct 76 ms 9400 KB Output is correct
12 Correct 78 ms 9880 KB Output is correct
13 Execution timed out 2074 ms 9756 KB Time limit exceeded

Subtask #6
0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 316 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 312 KB Output is correct
6 Correct 1 ms 460 KB Output is correct
7 Correct 2 ms 332 KB Output is correct
8 Correct 1 ms 460 KB Output is correct
9 Correct 2 ms 460 KB Output is correct
10 Correct 53 ms 7768 KB Output is correct
11 Correct 71 ms 9460 KB Output is correct
12 Correct 76 ms 9400 KB Output is correct
13 Correct 78 ms 9880 KB Output is correct
14 Execution timed out 2074 ms 9756 KB Time limit exceeded