Submission #2889494
Source Code Expand
#include <iostream> #include <vector> #include <queue> #include <algorithm> using namespace std; int root[4000]; int getRoot(int v){ return root[v] == -1 ? v : root[v] = getRoot(root[v]); } vector<vector<int>> solve(int N, const vector<pair<int, pair<int,int>>>& edge){ fill(root, root+N, -1); vector<vector<pair<int,int>>> g(N); int sum = 0; for(auto& e : edge){ int src = e.second.first; int dst = e.second.second; int p = getRoot(src); int q = getRoot(dst); if(p != q){ sum += e.first; root[q] = p; g[src].emplace_back(dst, e.first); g[dst].emplace_back(src, e.first); } } vector<vector<int>> res(N, vector<int>(N, -1)); for(int i=0;i<N;i++){ res[i][i] = 0; queue<int> qu; qu.push(i); while(!qu.empty()){ int pos = qu.front(); qu.pop(); for(auto& e : g[pos]){ int dst = e.first; if(res[i][dst] >= 0) continue; res[i][dst] = max(res[i][pos], e.second); qu.push(dst); } } } for(auto& v : res){ for(auto& t : v) t = sum - t; } return res; } int main(){ int N, M; while(cin >> N >> M){ vector<pair<int, pair<int, int>>> edge(M); for(auto& p : edge){ cin >> p.second.first >> p.second.second >> p.first; --p.second.first; --p.second.second; } sort(edge.begin(), edge.end()); auto res = solve(N, edge); int Q; cin >> Q; for(int i=0;i<Q;i++){ int s, t; cin >> s >> t; cout << res[s-1][t-1] << endl; } } }
Submission Info
Submission Time | |
---|---|
Task | A - Graph |
User | pes |
Language | C++14 (GCC 5.4.1) |
Score | 0 |
Code Size | 1473 Byte |
Status | WA |
Exec Time | 1000 ms |
Memory | 68864 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 | WA | 2 ms | 256 KB |
subtask_1_10.txt | WA | 569 ms | 65536 KB |
subtask_1_11.txt | AC | 1 ms | 256 KB |
subtask_1_2.txt | WA | 424 ms | 63616 KB |
subtask_1_3.txt | WA | 768 ms | 67840 KB |
subtask_1_4.txt | WA | 374 ms | 63232 KB |
subtask_1_5.txt | WA | 394 ms | 63232 KB |
subtask_1_6.txt | WA | 470 ms | 64384 KB |
subtask_1_7.txt | WA | 755 ms | 67840 KB |
subtask_1_8.txt | WA | 373 ms | 63232 KB |
subtask_1_9.txt | WA | 393 ms | 63232 KB |
subtask_2_1.txt | WA | 771 ms | 67840 KB |
subtask_2_2.txt | WA | 762 ms | 67840 KB |
subtask_2_3.txt | WA | 764 ms | 67840 KB |
subtask_2_4.txt | WA | 764 ms | 67840 KB |
subtask_2_5.txt | WA | 389 ms | 63232 KB |
subtask_2_6.txt | WA | 403 ms | 63488 KB |
subtask_2_7.txt | WA | 481 ms | 64384 KB |
subtask_2_8.txt | WA | 762 ms | 67840 KB |
subtask_3_1.txt | WA | 975 ms | 68864 KB |
subtask_3_2.txt | WA | 981 ms | 68864 KB |
subtask_3_3.txt | WA | 601 ms | 64384 KB |
subtask_3_4.txt | WA | 627 ms | 64512 KB |
subtask_3_5.txt | WA | 792 ms | 66560 KB |
subtask_3_6.txt | WA | 893 ms | 67712 KB |
subtask_3_7.txt | WA | 1000 ms | 68736 KB |
subtask_3_8.txt | WA | 988 ms | 68736 KB |