oj.uz

답안 #585568

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
585568 2022-06-29T05:13:56 Z 1ne 전선 연결 (IOI17_wiring) C++14
0 / 100
 1000 ms 204988 KB 
#include "wiring.h"
#include<bits/stdc++.h>
using namespace std;
struct node{
	long long u,v,cost;	
};
struct DSU{
	vector<int>parent;
	vector<int>sz;
	void build(int n){
		parent.resize(n);
		sz.resize(n);
		for (int i = 0;i<n;++i){
			parent[i] = i;
			sz[i] = 1;
		}
	}
	int findsets(int v){
		if (v == parent[v])return v;
		parent[v] = findsets(parent[v]);
		return parent[v];
	}
	bool unionset(int a,int b){
		int u = findsets(a);
		int v = findsets(b);
		if (u == v)return false;
		if (sz[u] < sz[v])swap(u,v);
		parent[v] = u;
		sz[u]+=sz[v];
		return true;
	}
};
long long min_total_length(std::vector<int> r, std::vector<int> b) {
	vector<node>edge;
	map<int,int>deg;
	long long ans = 0;
	for (auto x:r){
		for (auto y:b){
			edge.push_back({x,y,abs(x - y)});
			deg[x]++;
			deg[y]++;
			ans+=abs(x - y);
		}
	}
	sort(edge.begin(),edge.end(),[&](auto x,auto y){
		return x.cost > y.cost;
	});
	for (auto x:edge){
		if (deg[x.u] > 1 && deg[x.v] > 1){
			deg[x.u]--;
			deg[x.v]--;
			ans-=x.cost;
		}
	}
	return ans;
}

Subtask #1
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 212 KB 3rd lines differ - on the 1st token, expected: '25859', found: '37607'
2 Halted 0 ms 0 KB -

Subtask #2
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 212 KB 3rd lines differ - on the 1st token, expected: '904', found: '943'
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 212 KB 3rd lines differ - on the 1st token, expected: '316', found: '348'
2 Halted 0 ms 0 KB -

Subtask #4
0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Execution timed out 1096 ms 204988 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #5
0 / 45.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 212 KB 3rd lines differ - on the 1st token, expected: '25859', found: '37607'
2 Halted 0 ms 0 KB -