Submission #77539


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[5010], rank[5010];

    void init(){
	rep(i, 5000){
	    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 40
Code Size 1697 Byte
Status TLE
Exec Time 1645 ms
Memory 9780 KB

Judge Result

Set Name Subtask1 Subtask2 Subtask3 Subtask4
Score / Max Score 16 / 16 24 / 24 0 / 59 0 / 1
Status
AC × 9
AC × 15
AC × 15
TLE × 3
RE × 2
AC × 15
TLE × 6
RE × 4
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 24 ms 3060 KB
subtask1/2 AC 24 ms 3092 KB
subtask1/3 AC 23 ms 3088 KB
subtask1/4 AC 23 ms 3088 KB
subtask1/5 AC 55 ms 3128 KB
subtask1/6 AC 52 ms 3216 KB
subtask1/7 AC 53 ms 3212 KB
subtask1/8 AC 49 ms 3224 KB
subtask1/9 AC 53 ms 3124 KB
subtask2/1 AC 660 ms 4908 KB
subtask2/2 AC 546 ms 4800 KB
subtask2/3 AC 603 ms 4780 KB
subtask2/4 AC 446 ms 4796 KB
subtask2/5 AC 643 ms 4784 KB
subtask2/6 AC 68 ms 6052 KB
subtask3/1 TLE 1529 ms 5052 KB
subtask3/2 TLE 1645 ms 5112 KB
subtask3/3 TLE 1529 ms 5180 KB
subtask3/4 RE 1410 ms 5048 KB
subtask3/5 RE 1437 ms 4928 KB
subtask4/1 TLE 1541 ms 9464 KB
subtask4/2 TLE 1616 ms 9780 KB
subtask4/3 TLE 1528 ms 9404 KB
subtask4/4 RE 1500 ms 9272 KB
subtask4/5 RE 679 ms 8812 KB