Submission #3043770
Source Code Expand
#include <iostream>
#include <cstdio>
#include <queue>
#include <cmath>
#include <random>
#include <fstream>
#include <string>
#include <tuple>
#include <deque>
#include <set>
#include <map>
#include <stack>
#define REP(i, N) for(int i = 0; i< N; i++)
using namespace std;
#define ll long long
const int INF = 1 << 29;
const ll llINF = 10000000000000000;
const int MOD = 1000000007;
#define MAX_N 100100
typedef pair<int, int> P;
typedef pair<ll, ll> llP;
class UnionFindTree{
private:
int par[MAX_N];
int urank[MAX_N];
int size[MAX_N];
public:
int init(int n);
int find(int x);
int unite(int x, int y);
int same(int x, int y);
int parnum(int x){return par[x];}
int ranknum(int x){return urank[x];}
int sizenum(int x){return size[find(x)];}
};
int UnionFindTree::init(int n){
REP(i, n){
par[i] = i;
urank[i] = 0;
size[i] = 1;
}
return 0;
}
int UnionFindTree::find(int x){
if(par[x] == x)return x;
else return par[x] = find(par[x]);
}
int UnionFindTree::unite(int x, int y){
x = find(x);
y = find(y);
if(x == y)return 0;
if(urank[x] < urank[y]){
par[x] = y;
size[y] += size[x];
}else{
par[y] = x;
size[x] += size[y];
if(urank[x] == urank[y])urank[x] ++;
}
return 0;
}
int UnionFindTree::same(int x, int y){
return find(x) == find(y);
}
struct edge{int u, v, cost;};
bool comp(const edge& e1, const edge& e2){
return e1.cost < e2.cost;
}
int mediantree(int V, int E){
int median = 0;
vector<int> edgescost;
vector<edge> es;
REP(i, E){
int s, t, w;
cin >> s >> t >> w;
es.push_back(edge{s, t, w});
}
sort(es.begin(), es.end(), comp);
UnionFindTree tree;
tree.init(V);
int nagasa = 0;
REP(i, E){
edge e = es[i];
if(!tree.same(e.u, e.v)){
tree.unite(e.u, e.v);
edgescost.push_back(e.cost);
nagasa++;
}
}
if(nagasa % 2 == 0)median = (edgescost[nagasa/2] + edgescost[nagasa/2 + 1]) / 2;
else median = edgescost[(nagasa - 1) / 2];
return median;
}
struct point{int number, x, y;};
bool xjisho(const point& p1, const point& p2){
return p1.x < p2.x || (p1.x == p2.x && p1.y < p2.y);
}
bool yjisho(const point& p1, const point& p2){
return p1.y < p2.y || (p1.y == p2.y && p1.x < p2.x);
}
int mahounoito(){
vector<edge> es1;
int V, E;
cin >> V >> E;
REP(i, E){
int s, t, w;
cin >> s >> t >> w;
es1.push_back(edge{s, t, w});
}
int Q;
int res = 0;
cin >> Q;
UnionFindTree queries;
queries.init(V);
int query = 0;
vector<int> ress;
vector<P> tunagattenai;
vector<edge> es;
REP(query, Q){
int p,q;
cin >> p >> q;
queries.unite(p, q);
tunagattenai.push_back(P(p,q));
REP(i, E){
if(queries.same(es1.back().u, es1.back().v)){
es.push_back(es1.back());
es1.pop_back();
}
}
sort(es.begin(), es.end(), comp);
UnionFindTree tree;
tree.init(V);
res = 0;
REP(i, es.size()){
edge e = es[i];
if(!tree.same(e.u, e.v)){
tree.unite(e.u, e.v);
res += e.cost;
}
}
bool ok = true;
REP(i, tunagattenai.size()){
if(tree.same(tunagattenai.back().first, tunagattenai.back().second))tunagattenai.pop_back();
else ok = false;
}
if(ok)ress.push_back(res);
else ress.push_back(-1);
}
REP(i, ress.size()){
if(ress[i] == -1)printf("IMPOSSIBLE\n");
else printf("%d\n", ress[i]);
}
return res;
}
int gameonagrid(){
vector<edge> es;
int H, W, S, G;
cin >> H >> W;
int Sx, Sy, Gx, Gy;
cin >> Sx >> Sy;
S = Sx + Sy * W;
cin >> Gx >> Gy;
G = Gx + Gy * W;
int P[10100] = {0};
int res = 0;
REP(i, W * H){
int p;
cin >> p;
P[i] = -p;
res += P[i];
}
REP(i, H * W){
if(i >= W){
es.push_back(edge{i, i - W, -P[i] * P[i - W]});
es.push_back(edge{i - W, i, -P[i] * P[i - W]});
}
if(i < (H - 1) * W){
es.push_back(edge{i, i + W, -P[i] * P[i + W]});
es.push_back(edge{i + W, i, -P[i] * P[i + W]});
}
if(i % W != 0){
es.push_back(edge{i, i - 1, -P[i] * P[i - 1]});
es.push_back(edge{i - 1, i, -P[i] * P[i - 1]});
}
if(i % W != W - 1){
es.push_back(edge{i, i + 1, -P[i] * P[i + 1]});
es.push_back(edge{i + 1, i, -P[i] * P[i + 1]});
}
}
sort(es.begin(), es.end(), comp);
UnionFindTree tree;
tree.init(W * H);
REP(i, es.size()){
edge e = es[i];
if(!tree.same(e.u, e.v)){
tree.unite(e.u, e.v);
res += e.cost;
}
}
return -res;
}
int built(){
vector<point> town;
vector<edge> es;
int N, E;
cin >> N;
E = 2 * (N - 1);
REP(i, N){
int x, y;
cin >> x >> y;
town.push_back(point{i,x,y});
}
sort(town.begin(), town.end(), xjisho);
REP(i, N - 1){
es.push_back(edge{town[i].number, town[i + 1].number, min(abs(town[i].x - town[i + 1].x),abs(town[i].y - town[i + 1].y))});
}
sort(town.begin(), town.end(), yjisho);
REP(i, N - 1){
es.push_back(edge{town[i].number, town[i + 1].number, min(abs(town[i].x - town[i + 1].x),abs(town[i].y - town[i + 1].y))});
}
sort(es.begin(), es.end(), comp);
UnionFindTree tree;
tree.init(N);
int res = 0;
REP(i, E){
edge e = es[i];
if(!tree.same(e.u, e.v)){
tree.unite(e.u, e.v);
res += e.cost;
}
}
return res;
}
int kruskal(){
vector<edge> es;
int V, E;
cin >> V >> E;
REP(i, E){
int s, t, w;
cin >> s >> t >> w;
es.push_back(edge{s, t, w});
}
sort(es.begin(), es.end(), comp);
UnionFindTree tree;
tree.init(V);
int res = 0;
REP(i, E){
edge e = es[i];
if(!tree.same(e.u, e.v)){
tree.unite(e.u, e.v);
res += e.cost;
}
}
return res;
}
int prim(){
struct edge {int to, cost;};
vector<edge> e[MAX_N];
int mincost[MAX_N];
bool used[MAX_N];
int N, E;
cin >> N >> E;
REP(i, N){
mincost[i] = INF;
used[i] = false;
}
REP(i, E){
int s, t, w;
cin >> s >> t >> w;
edge ss = {t, w};
edge tt = {s, w};
e[s].push_back(ss);
e[t].push_back(tt);
}
mincost[0] = 0;
int res = 0;
priority_queue<P, vector<P>, greater<P>> que;
REP(i, e[0].size()){
que.push(P(e[0][i].cost,e[0][i].to));
}
used[0] = true;
int vnokazu = 1;
while(vnokazu < N){
P p;
do{
p = que.top();que.pop();
}while(used[p.second]);
used[p.second] = true;
res += p.first;
vnokazu++;
REP(i, e[p.second].size()){
if(!used[e[p.second][i].to])que.push(P(e[p.second][i].cost,e[p.second][i].to));
}
}
return res;
}
int main(){
mahounoito();
}
Submission Info
Submission Time |
|
Task |
F - 魔法の糸 |
User |
hyamamoto277 |
Language |
C++14 (Clang 3.8.0) |
Score |
0 |
Code Size |
7648 Byte |
Status |
RE |
Exec Time |
2103 ms |
Memory |
8048 KB |
Judge Result
Set Name |
All |
Score / Max Score |
0 / 200 |
Status |
AC |
× 2 |
WA |
× 9 |
TLE |
× 12 |
RE |
× 8 |
|
Set Name |
Test Cases |
All |
00-sample1, 00-sample2, 01-random-small-tree01, 01-random-small-tree02, 02-random-small-sparse01, 02-random-small-sparse02, 02-random-small-sparse03, 03-random-small-dense01, 03-random-small-dense02, 03-random-small-dense03, 03-random-small-dense04, 03-random-small-dense05, 11-random-large-tree01, 11-random-large-tree02, 11-random-large-tree03, 12-random-large-sparse01, 12-random-large-sparse02, 12-random-large-sparse03, 13-random-large-denseA01, 13-random-large-denseA02, 13-random-large-denseA03, 13-random-large-denseA04, 14-random-large-denseB01, 14-random-large-denseB02, 14-random-large-denseB03, 14-random-large-denseB04, 15-random-large-denseC01, 15-random-large-denseC02, 20-kill-naive, 21-kill-loop, 23-min |
Case Name |
Status |
Exec Time |
Memory |
00-sample1 |
WA |
1 ms |
256 KB |
00-sample2 |
WA |
1 ms |
256 KB |
01-random-small-tree01 |
AC |
2 ms |
256 KB |
01-random-small-tree02 |
RE |
101 ms |
256 KB |
02-random-small-sparse01 |
RE |
96 ms |
256 KB |
02-random-small-sparse02 |
WA |
3 ms |
256 KB |
02-random-small-sparse03 |
RE |
98 ms |
256 KB |
03-random-small-dense01 |
WA |
8 ms |
384 KB |
03-random-small-dense02 |
WA |
7 ms |
384 KB |
03-random-small-dense03 |
WA |
8 ms |
384 KB |
03-random-small-dense04 |
WA |
8 ms |
384 KB |
03-random-small-dense05 |
WA |
8 ms |
384 KB |
11-random-large-tree01 |
RE |
152 ms |
768 KB |
11-random-large-tree02 |
WA |
53 ms |
512 KB |
11-random-large-tree03 |
RE |
147 ms |
2432 KB |
12-random-large-sparse01 |
RE |
471 ms |
1148 KB |
12-random-large-sparse02 |
RE |
474 ms |
1148 KB |
12-random-large-sparse03 |
RE |
418 ms |
1148 KB |
13-random-large-denseA01 |
TLE |
2103 ms |
4340 KB |
13-random-large-denseA02 |
TLE |
2103 ms |
3956 KB |
13-random-large-denseA03 |
TLE |
2103 ms |
4596 KB |
13-random-large-denseA04 |
TLE |
2103 ms |
3444 KB |
14-random-large-denseB01 |
TLE |
2103 ms |
4980 KB |
14-random-large-denseB02 |
TLE |
2103 ms |
4212 KB |
14-random-large-denseB03 |
TLE |
2103 ms |
4852 KB |
14-random-large-denseB04 |
TLE |
2103 ms |
3444 KB |
15-random-large-denseC01 |
TLE |
2103 ms |
3444 KB |
15-random-large-denseC02 |
TLE |
2103 ms |
4468 KB |
20-kill-naive |
TLE |
2103 ms |
8048 KB |
21-kill-loop |
TLE |
2103 ms |
3444 KB |
23-min |
AC |
1 ms |
256 KB |