# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
584696 |
2022-06-27T20:34:15 Z |
1ne |
Wiring (IOI17_wiring) |
C++14 |
|
1 ms |
300 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<pair<int,int>>arr;
for (auto x:r){
arr.push_back({x,0});
}
for (auto x:b){
arr.push_back({x,1});
}
map<long long,long long>minny;
vector<node>edge;
long long rr = -1,bb = -1;
sort(arr.begin(),arr.end());
for (auto x:arr){
if (x.second == 0){
if (bb!=-1){
edge.push_back({x.first,bb,x.first - bb});
minny[x.first] = x.first - bb;
}
rr = x.first;
}
else{
if (rr!=-1){
edge.push_back({x.first,rr,x.first - rr});
minny[x.first] = x.first - rr;
}
bb = x.first;
}
}
sort(arr.rbegin(),arr.rend());
rr = -1,bb =-1;
for (auto x:arr){
if (x.second == 0){
if (bb!=-1){
edge.push_back({x.first,bb,bb - x.first});
minny[x.first] = min(minny[x.first],bb - x.first);
}
rr = x.first;
}
else{
if (rr!=-1){
edge.push_back({x.first,rr,rr - x.first});
minny[x.first] = min(minny[x.first],rr - x.first);
}
bb = x.first;
}
}
sort(edge.begin(),edge.end(),[&](auto x,auto y){
return x.cost < y.cost;
});
map<long long,bool>mp;
int64_t ans = 0;
for (auto x:edge){
if (!mp[x.u] && !mp[x.v]){
mp[x.u] = true;
mp[x.v] = true;
ans+=x.cost;
}
}
set<int>brr;
for (auto x:b){
if (!mp[x]){
brr.insert(x);
}
}
const long long maxn = 1e15;
for (auto x:r){
if (!mp[x]){
int64_t dist = maxn;
int64_t index = maxn;
for (auto y:brr){
if (y - x<dist){
index = y;
dist = y - x;
}
}
if (index ==maxn){
ans+=minny[x];
}
else if (minny[x] + minny[index] < dist){
ans+=minny[x];
}
else{
ans+=dist;
brr.erase(index);
}
}
}
for (auto x:brr)ans+=minny[x];
return ans;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
1 ms |
300 KB |
3rd lines differ - on the 1st token, expected: '25859', found: '-6220' |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
1 ms |
212 KB |
3rd lines differ - on the 1st token, expected: '904', found: '326' |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
0 ms |
212 KB |
3rd lines differ - on the 1st token, expected: '316', found: '188' |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
0 ms |
212 KB |
3rd lines differ - on the 1st token, expected: '27', found: '-10' |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
1 ms |
300 KB |
3rd lines differ - on the 1st token, expected: '25859', found: '-6220' |
2 |
Halted |
0 ms |
0 KB |
- |