Submission #2279325


Source Code Expand

#include <bits/stdc++.h>
using namespace std;

typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef pair<int, int> PII;
typedef long long LL;
typedef pair<LL, LL> PLL;

#define ALL(a)  (a).begin(),(a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define PB push_back
#define EB emplace_back
#define MP make_pair
#define SZ(a) int((a).size())
#define SORT(c) sort((c).begin(),(c).end())

#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)

#define FF first
#define SS second
template<class S, class T>
istream& operator>>(istream& is, pair<S,T>& p){
  return is >> p.FF >> p.SS;
}

const double EPS = 1e-10;
const double PI  = acos(-1.0);
const LL MOD = 1e9+7;

class UnionFind{
private:
  vector<int> par, rank;
public:
  UnionFind(int n){
	par.assign(n, 0);
	rank.assign(n, 0);
	for(int i=0;i<n;++i)
	  par[i] = i;
  }

  //find root of x
  int find(int x){
	if(par[x] == x)
	  return x;
	return (par[x] = find(par[x]));
  }

  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;
	  if(rank[x] == rank[y])
		++rank[x];
	}
  }

  bool same(int x, int y){
	return find(x) == find(y);
  }
};

struct Edge{
  int to;
  LL cost;

  Edge(int t, LL c): to(t), cost(c)
  {}
  bool operator>(const Edge& rhs) const{
	return cost > rhs.cost;
  }
  bool operator<(const Edge& rhs) const{
	return cost < rhs.cost;
  }

};
typedef vector< vector<Edge> > Graph;

// 無向グラフのとき
void add_edge(Graph& graph, int u, int v, LL cost){
  graph[u].push_back(Edge(v,cost));
  graph[v].push_back(Edge(u,cost));
}

vector<pair<Edge,int>> edges;
LL kruskal(const Graph& G, Graph& G_){
  int N = SZ(G);
  UnionFind uf(N);

  LL res = 0, i, n = 0;
  for(i=0;i<SZ(edges);++i){
	auto& e = edges[i].first;
	int v = edges[i].second;
	if(!uf.same(e.to,v)){
	  uf.unite(e.to, v);
	  res += e.cost;
	  add_edge(G_, e.to, v, e.cost);
	}
  }
  return res;
}

LL dist[4010][4010];
void dfs(int s, int p, int u, LL mx, Graph& G){
  dist[s][u] = dist[u][s] = max(dist[s][u], mx);
  for(auto& e: G[u]){
	if(e.to == p) continue;
	dfs(s, u, e.to, max(mx,e.cost), G);
  }
}

int main(){
  cin.tie(0);
  ios_base::sync_with_stdio(false);

  int N, M; cin >> N >> M;
  Graph G(N), G_(N);
  REP(i,M){
	int a, b, c; cin >> a >> b >> c;
	--a; --b;
	add_edge(G, a, b, c);
	edges.push_back(MP(G[a].back(), a));
	edges.push_back(MP(G[b].back(), b));
  }
  sort(ALL(edges));

  LL mx = kruskal(G,G_);
  REP(i,N) dfs(i,-1,i,0,G_);
  int Q; cin >> Q;
  while(Q--){
	LL s,t; cin >> s >> t;
	--s, --t;

	cout << mx - dist[s][t] << endl;
  }

  return 0;
}

Submission Info

Submission Time
Task A - Graph
User okaduki
Language C++14 (GCC 5.4.1)
Score 700
Code Size 2796 Byte
Status AC
Exec Time 996 ms
Memory 165284 KB

Judge Result

Set Name Sample subtask1 subtask2 All
Score / Max Score 0 / 0 200 / 200 300 / 300 200 / 200
Status
AC × 2
AC × 12
AC × 21
AC × 31
Set Name Test Cases
Sample sample_1.txt, sample_2.txt
subtask1 sample_2.txt, subtask_1_1.txt, subtask_1_10.txt, subtask_1_11.txt, subtask_1_2.txt, subtask_1_3.txt, subtask_1_4.txt, subtask_1_5.txt, subtask_1_6.txt, subtask_1_7.txt, subtask_1_8.txt, subtask_1_9.txt
subtask2 sample_1.txt, sample_2.txt, subtask_1_1.txt, subtask_1_10.txt, subtask_1_11.txt, subtask_1_2.txt, subtask_1_3.txt, subtask_1_4.txt, subtask_1_5.txt, subtask_1_6.txt, subtask_1_7.txt, subtask_1_8.txt, subtask_1_9.txt, subtask_2_1.txt, subtask_2_2.txt, subtask_2_3.txt, subtask_2_4.txt, subtask_2_5.txt, subtask_2_6.txt, subtask_2_7.txt, subtask_2_8.txt
All sample_1.txt, sample_2.txt, sample_1.txt, sample_2.txt, subtask_1_1.txt, subtask_1_10.txt, subtask_1_11.txt, subtask_1_2.txt, subtask_1_3.txt, subtask_1_4.txt, subtask_1_5.txt, subtask_1_6.txt, subtask_1_7.txt, subtask_1_8.txt, subtask_1_9.txt, subtask_2_1.txt, subtask_2_2.txt, subtask_2_3.txt, subtask_2_4.txt, subtask_2_5.txt, subtask_2_6.txt, subtask_2_7.txt, subtask_2_8.txt, subtask_3_1.txt, subtask_3_2.txt, subtask_3_3.txt, subtask_3_4.txt, subtask_3_5.txt, subtask_3_6.txt, subtask_3_7.txt, subtask_3_8.txt
Case Name Status Exec Time Memory
sample_1.txt AC 1 ms 256 KB
sample_2.txt AC 1 ms 256 KB
subtask_1_1.txt AC 2 ms 2688 KB
subtask_1_10.txt AC 693 ms 144808 KB
subtask_1_11.txt AC 1 ms 256 KB
subtask_1_2.txt AC 603 ms 129712 KB
subtask_1_3.txt AC 810 ms 163876 KB
subtask_1_4.txt AC 532 ms 126336 KB
subtask_1_5.txt AC 561 ms 126524 KB
subtask_1_6.txt AC 629 ms 136364 KB
subtask_1_7.txt AC 785 ms 163748 KB
subtask_1_8.txt AC 526 ms 126464 KB
subtask_1_9.txt AC 576 ms 126904 KB
subtask_2_1.txt AC 812 ms 163748 KB
subtask_2_2.txt AC 801 ms 164004 KB
subtask_2_3.txt AC 809 ms 162340 KB
subtask_2_4.txt AC 819 ms 162980 KB
subtask_2_5.txt AC 535 ms 126464 KB
subtask_2_6.txt AC 595 ms 127924 KB
subtask_2_7.txt AC 640 ms 135340 KB
subtask_2_8.txt AC 805 ms 162596 KB
subtask_3_1.txt AC 979 ms 165028 KB
subtask_3_2.txt AC 981 ms 165284 KB
subtask_3_3.txt AC 724 ms 127744 KB
subtask_3_4.txt AC 751 ms 128184 KB
subtask_3_5.txt AC 865 ms 146472 KB
subtask_3_6.txt AC 923 ms 160164 KB
subtask_3_7.txt AC 996 ms 164772 KB
subtask_3_8.txt AC 973 ms 164260 KB