Submission #77529
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; } 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 - 1){ int v = i + 1; rep(j, g[v].size()){ eg.pb(edge(i, g[v][j].fi, g[v][j].se)); } sort(eg.begin(), eg.end(), cmp); uf.init(); int sz = v + 1; ll ans = 0; rep(j, eg.size()){ edge crt = eg[j]; if(uf.same(crt.f, crt.t)) continue; uf.unite(crt.f, crt.t); --sz; ans += crt.c; } if(sz != 0){ 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 | 0 |
Code Size | 1506 Byte |
Status | WA |
Exec Time | 1547 ms |
Memory | 10524 KB |
Judge Result
Set Name | Subtask1 | Subtask2 | Subtask3 | Subtask4 | ||||||||||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Score / Max Score | 0 / 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 | WA | 29 ms | 3940 KB |
subtask1/2 | AC | 25 ms | 3004 KB |
subtask1/3 | AC | 26 ms | 3856 KB |
subtask1/4 | WA | 26 ms | 3864 KB |
subtask1/5 | WA | 425 ms | 3984 KB |
subtask1/6 | WA | 334 ms | 3872 KB |
subtask1/7 | WA | 439 ms | 3980 KB |
subtask1/8 | WA | 449 ms | 3996 KB |
subtask1/9 | AC | 386 ms | 3884 KB |
subtask2/1 | TLE | 1529 ms | 5684 KB |
subtask2/2 | TLE | 1530 ms | 5624 KB |
subtask2/3 | TLE | 1530 ms | 5624 KB |
subtask2/4 | TLE | 1529 ms | 5748 KB |
subtask2/5 | TLE | 1529 ms | 5684 KB |
subtask2/6 | WA | 73 ms | 6060 KB |
subtask3/1 | TLE | 1530 ms | 5688 KB |
subtask3/2 | TLE | 1530 ms | 5808 KB |
subtask3/3 | TLE | 1529 ms | 5812 KB |
subtask3/4 | TLE | 1531 ms | 5812 KB |
subtask3/5 | TLE | 1530 ms | 5636 KB |
subtask4/1 | TLE | 1531 ms | 10028 KB |
subtask4/2 | TLE | 1531 ms | 10524 KB |
subtask4/3 | TLE | 1530 ms | 10040 KB |
subtask4/4 | TLE | 1532 ms | 10040 KB |
subtask4/5 | TLE | 1547 ms | 9652 KB |