Submission #1534810
Source Code Expand
#pragma GCC optimize ("O3")
#pragma GCC target ("avx")
#include "bits/stdc++.h" // define macro "/D__MAI"
using namespace std;
typedef long long int ll;
#define xprintf(fmt,...) fprintf(stderr,fmt,__VA_ARGS__)
#define debugv(v) {printf("L%d %s > ",__LINE__,#v);for(auto e:v){cout<<e<<" ";}cout<<endl;}
#define debuga(m,w) {printf("L%d %s > ",__LINE__,#m);for(int x=0;x<(w);x++){cout<<(m)[x]<<" ";}cout<<endl;}
#define debugaa(m,h,w) {printf("L%d %s >\n",__LINE__,#m);for(int y=0;y<(h);y++){for(int x=0;x<(w);x++){cout<<(m)[y][x]<<" ";}cout<<endl;}}
#define ALL(v) (v).begin(),(v).end()
#define repeat(cnt,l) for(auto cnt=0ll;cnt<(l);++cnt)
#define iterate(cnt,b,e) for(auto cnt=(b);cnt!=(e);++cnt)
#define MD 1000000007ll
#define PI 3.1415926535897932384626433832795
template<typename T1, typename T2> ostream& operator <<(ostream &o, const pair<T1, T2> p) { o << "(" << p.first << ":" << p.second << ")"; return o; }
template<typename iterator> inline size_t argmin(iterator begin, iterator end) {
return distance(begin, min_element(begin, end));
}
template<typename iterator> inline size_t argmax(iterator begin, iterator end) {
return distance(begin, max_element(begin, end));
}
template<typename T> T& maxset(T& to, const T& val) { return to = max(to, val); }
template<typename T> T& minset(T& to, const T& val) { return to = min(to, val); }
mt19937_64 randdev(8901016);
inline ll rand_range(ll l, ll h) {
return uniform_int_distribution<ll>(l, h)(randdev);
}
#ifdef __MAI
#define getchar_unlocked getchar
#define putchar_unlocked putchar
#endif
#ifdef __VSCC
#define getchar_unlocked _getchar_nolock
#define putchar_unlocked _putchar_nolock
#endif
namespace {
#define isvisiblechar(c) (0x21<=(c)&&(c)<=0x7E)
class MaiScanner {
public:
template<typename T> void input_integer(T& var) {
var = 0;
T sign = 1;
int cc = getchar_unlocked();
for (; cc<'0' || '9'<cc; cc = getchar_unlocked())
if (cc == '-') sign = -1;
for (; '0' <= cc&&cc <= '9'; cc = getchar_unlocked())
var = (var << 3) + (var << 1) + cc - '0';
var = var*sign;
}
inline int c() { return getchar_unlocked(); }
inline MaiScanner& operator>>(int& var) {
input_integer<int>(var);
return *this;
}
inline MaiScanner& operator>>(long long& var) {
input_integer<long long>(var);
return *this;
}
inline MaiScanner& operator>>(string& var) {
int cc = getchar_unlocked();
for (; !isvisiblechar(cc); cc = getchar_unlocked());
for (; isvisiblechar(cc); cc = getchar_unlocked())
var.push_back(cc);
}
template<typename IT> void in(IT begin, IT end) {
for (auto it = begin; it != end; ++it) *this >> *it;
}
};
}
MaiScanner scanner;
class Graph2d {
public:
typedef ll numeric;
size_t n;
vector<numeric> matrix;
Graph2d(size_t size) :n(size), matrix(size*size) {};
void resize(size_t s) {
n = s;
matrix.resize(n*n);
}
inline numeric& at(int y, int x) { return matrix[y*n + x]; }
inline numeric& operator()(int y, int x) { return matrix[y*n + x]; }
inline numeric at(int y, int x) const { return matrix[y*n + x]; }
inline numeric operator()(int y, int x) const { return matrix[y*n + x]; }
inline void connect(int u, int v, int dist = 1) {
at(u, v) = at(v, u) = dist;
}
inline void connect_d(int from, int to, int dist = 1) { // directedEdge u->v
at(from, to) = dist;
}
};
class Graph {
public:
size_t n;
vector<vector<int>> vertex_to;
Graph(size_t n) :n(n), vertex_to(n) {}
void connect(int from, int to) {
vertex_to[from].emplace_back(to);
vertex_to[to].emplace_back(from);
}
void resize(size_t _n) {
n = _n;
vertex_to.resize(_n);
}
};
void warshall_floyd(Graph2d& g) {
int i, j, k;
for (i = 0; i < g.n; i++) {
for (j = 0; j < g.n; j++) {
for (k = 0; k < g.n; k++) {
g(j, k) = min(g(j, k), g(j, i) + g(i, k));
}
}
}
}
class unionfind {
public:
vector<int> data;
unionfind(int size) : data(size, -1) { }
bool union_set(int x, int y) {
x = root(x); y = root(y);
if (x != y) {
if (data[y] < data[x]) swap(x, y);
data[x] += data[y]; data[y] = x;
}
return x != y;
}
inline bool find_set(int x, int y) {
return root(x) == root(y);
}
inline int root(int x) {
return data[x] < 0 ? x : data[x] = root(data[x]);
}
inline int size(int x) {
return -data[root(x)];
}
};
int m, n, kei;
Graph2d graph_mat(1);
Graph graph(1);
vector<vector<ll>> edges;
ll answer[4040][4040];
void build() {
Graph tree(n);
unionfind uf(n);
ll total = 0;
for (int i = 0, cnt = 0; cnt < n - 1; ++i) {
auto& v = edges[i];
if (uf.union_set(v[1], v[2])) {
tree.connect(v[1], v[2]);
++cnt;
total += v[0];
}
}
function<void(int, int, int, ll)> dfs = [&](int start, int idx,int from, ll wmax) {
answer[start][idx] = total - wmax;
answer[idx][start] = total - wmax;
for (int to : tree.vertex_to[idx]) {
if (from == to) continue;
dfs(start, to, idx, max(wmax, graph_mat(idx, to)));
}
};
for (int i = 0; i < n; ++i) {
dfs(i, i, 4010, 0);
}
}
int main() {
scanner >> n >> m;
graph_mat.resize(n);
graph.resize(n);
fill(ALL(graph_mat.matrix), 5e15);
repeat(i, m) {
ll a, b, c;
scanner >> a >> b >> c;
--a; --b;
graph_mat.connect(a, b, c);
graph.connect(a, b);
edges.push_back({ c,a,b });
}
sort(ALL(edges));
build();
ll nq;
scanner >> nq;
repeat(qi, nq) {
ll u, v;
scanner >> u >> v;
--u; --v;
cout << answer[u][v] << '\n';
}
return 0;
}
Submission Info
Submission Time |
|
Task |
A - Graph |
User |
m_buyoh |
Language |
C++14 (GCC 5.4.1) |
Score |
0 |
Code Size |
6356 Byte |
Status |
MLE |
Exec Time |
1031 ms |
Memory |
281384 KB |
Judge Result
Set Name |
Sample |
subtask1 |
subtask2 |
All |
Score / Max Score |
0 / 0 |
0 / 200 |
0 / 300 |
0 / 200 |
Status |
|
|
|
|
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 |
2816 KB |
subtask_1_10.txt |
MLE |
919 ms |
267052 KB |
subtask_1_11.txt |
AC |
1 ms |
256 KB |
subtask_1_2.txt |
AC |
816 ms |
254644 KB |
subtask_1_3.txt |
MLE |
1018 ms |
279848 KB |
subtask_1_4.txt |
AC |
760 ms |
252928 KB |
subtask_1_5.txt |
AC |
791 ms |
252288 KB |
subtask_1_6.txt |
MLE |
832 ms |
259248 KB |
subtask_1_7.txt |
MLE |
1011 ms |
279080 KB |
subtask_1_8.txt |
AC |
729 ms |
252928 KB |
subtask_1_9.txt |
AC |
783 ms |
253244 KB |
subtask_2_1.txt |
MLE |
1005 ms |
279848 KB |
subtask_2_2.txt |
MLE |
1005 ms |
279848 KB |
subtask_2_3.txt |
MLE |
1002 ms |
279720 KB |
subtask_2_4.txt |
MLE |
1008 ms |
279976 KB |
subtask_2_5.txt |
AC |
748 ms |
252928 KB |
subtask_2_6.txt |
AC |
786 ms |
254008 KB |
subtask_2_7.txt |
MLE |
818 ms |
259248 KB |
subtask_2_8.txt |
MLE |
1018 ms |
280232 KB |
subtask_3_1.txt |
MLE |
1022 ms |
281384 KB |
subtask_3_2.txt |
MLE |
1018 ms |
281000 KB |
subtask_3_3.txt |
AC |
763 ms |
254096 KB |
subtask_3_4.txt |
AC |
796 ms |
254524 KB |
subtask_3_5.txt |
MLE |
908 ms |
268204 KB |
subtask_3_6.txt |
MLE |
956 ms |
274984 KB |
subtask_3_7.txt |
MLE |
1020 ms |
281384 KB |
subtask_3_8.txt |
MLE |
1031 ms |
280744 KB |