Submission #77538
Source Code Expand
#include <vector>
#include <algorithm>
#include "grader.h"
using namespace std;
#define rep(i, n) for(int i = 0; i < (int)n; ++i)
#define fi first
#define se second
#define mp make_pair
#define pb push_back
typedef pair<int, int> P;
typedef long long ll;
vector<P> g[100010];
struct unionfind{
int par[100010], rank[100010];
void init(){
rep(i, 100000){
par[i] = i;
rank[i] = 0;
}
}
inline int find(int x){
if(par[x] == x) return x;
return par[x] = find(par[x]);
}
inline void unite(int x, int y){
x = find(x), y = find(y);
if(x == y) return ;
if(rank[x] < rank[y]) par[x] = y;
else {
par[y] = x;
rank[x] += (rank[x] == rank[y]);
}
}
inline bool same(int a, int b){ return find(a) == find(b); }
}uf;
struct edge{
int f, t, c;
edge(int f, int t, int c) : f(f), t(t), c(c){}
edge(){}
};
bool cmp(edge a, edge b){ return a.c < b.c; }
bool cal(P a, P b){ return a.se < b.se; }
vector<edge> eg;
void construct(int n, int m, int e[][3]){
rep(i, m) g[e[i][1]].pb(mp(e[i][0], e[i][2]));
rep(i, n) sort(g[i].begin(), g[i].end(), cal);
rep(i, n - 1){
int v = i + 1;
vector<edge> a, b;
a.resize(g[v].size() + eg.size());
rep(j, g[v].size()) b.pb(edge(v, g[v][j].fi, g[v][j].se));
merge(eg.begin(), eg.end(), b.begin(), b.end(), a.begin(), cmp);
eg.clear();
uf.init();
int sz = v + 1;
ll ans = 0;
rep(j, a.size()){
edge crt = a[j];
if(uf.same(crt.f, crt.t)) continue;
eg.pb(crt);
uf.unite(crt.f, crt.t);
--sz;
ans += crt.c;
}
if(sz != 1){
answer(-1);
}else{
answer(ans);
}
}
}
Submission Info
Judge Result
Set Name |
Subtask1 |
Subtask2 |
Subtask3 |
Subtask4 |
Score / Max Score |
16 / 16 |
0 / 24 |
0 / 59 |
0 / 1 |
Status |
|
|
|
|
Set Name |
Test Cases |
Subtask1 |
subtask1/1, subtask1/2, subtask1/3, subtask1/4, subtask1/5, subtask1/6, subtask1/7, subtask1/8, subtask1/9 |
Subtask2 |
subtask1/1, subtask1/2, subtask1/3, subtask1/4, subtask1/5, subtask1/6, subtask1/7, subtask1/8, subtask1/9, subtask2/1, subtask2/2, subtask2/3, subtask2/4, subtask2/5, subtask2/6 |
Subtask3 |
subtask1/1, subtask1/2, subtask1/3, subtask1/4, subtask1/5, subtask1/6, subtask1/7, subtask1/8, subtask1/9, subtask2/1, subtask2/2, subtask2/3, subtask2/4, subtask2/5, subtask2/6, subtask3/1, subtask3/2, subtask3/3, subtask3/4, subtask3/5 |
Subtask4 |
subtask1/1, subtask1/2, subtask1/3, subtask1/4, subtask1/5, subtask1/6, subtask1/7, subtask1/8, subtask1/9, subtask2/1, subtask2/2, subtask2/3, subtask2/4, subtask2/5, subtask2/6, subtask3/1, subtask3/2, subtask3/3, subtask3/4, subtask3/5, subtask4/1, subtask4/2, subtask4/3, subtask4/4, subtask4/5 |
Case Name |
Status |
Exec Time |
Memory |
subtask1/1 |
AC |
57 ms |
3852 KB |
subtask1/2 |
AC |
25 ms |
2996 KB |
subtask1/3 |
AC |
24 ms |
3856 KB |
subtask1/4 |
AC |
27 ms |
3836 KB |
subtask1/5 |
AC |
265 ms |
3984 KB |
subtask1/6 |
AC |
250 ms |
3864 KB |
subtask1/7 |
AC |
250 ms |
3880 KB |
subtask1/8 |
AC |
243 ms |
3972 KB |
subtask1/9 |
AC |
248 ms |
4016 KB |
subtask2/1 |
TLE |
1561 ms |
5684 KB |
subtask2/2 |
TLE |
1519 ms |
5548 KB |
subtask2/3 |
TLE |
1530 ms |
5688 KB |
subtask2/4 |
AC |
1433 ms |
5552 KB |
subtask2/5 |
TLE |
1530 ms |
5688 KB |
subtask2/6 |
AC |
71 ms |
6688 KB |
subtask3/1 |
TLE |
1529 ms |
5808 KB |
subtask3/2 |
TLE |
1532 ms |
5944 KB |
subtask3/3 |
TLE |
1529 ms |
5808 KB |
subtask3/4 |
TLE |
1529 ms |
5812 KB |
subtask3/5 |
TLE |
1529 ms |
5688 KB |
subtask4/1 |
TLE |
1530 ms |
10172 KB |
subtask4/2 |
TLE |
1530 ms |
10548 KB |
subtask4/3 |
TLE |
1530 ms |
10160 KB |
subtask4/4 |
TLE |
1530 ms |
10164 KB |
subtask4/5 |
TLE |
1530 ms |
9644 KB |