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

Submission Time
Task A - かえってきたどうぶつたち と しんりんのさいせい (Return of Animals and Regeneration of Forests)
User satashun
Language IOI-Style C++ (GCC 5.4.1)
Score 16
Code Size 1703 Byte
Status TLE
Exec Time 1561 ms
Memory 10548 KB

Judge Result

Set Name Subtask1 Subtask2 Subtask3 Subtask4
Score / Max Score 16 / 16 0 / 24 0 / 59 0 / 1
Status
AC × 9
AC × 11
TLE × 4
AC × 11
TLE × 9
AC × 11
TLE × 14
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