| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 581324 |
2022-06-22T13:17:56 Z |
79brue |
Toll (APIO13_toll) |
C++17 |
|
2500 ms |
12580 KB |
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
struct unionFind{
int par[100002];
void init(int _n){
for(int i=0; i<=_n; i++) par[i]=i;
}
int find(int x){
if(x==par[x]) return x;
return par[x] = find(par[x]);
}
void merge(int x, int y){
x = find(x), y = find(y);
par[x] = y;
}
} dsu, dsu2;
struct Edge{
int x, y; ll z;
Edge(){}
Edge(int x, int y, ll z): x(x), y(y), z(z){}
bool operator<(const Edge &r)const{
return z<r.z;
}
};
int n, m, k;
unordered_set<ll> st;
Edge edge[500002];
int ex[22], ey[22];
int root;
ll arr[100002];
ll ans;
vector<pair<int, ll> > rLink[100002];
vector<pair<int, int> > nLink[100002];
void input(){
scanf("%d %d %d", &n, &m, &k);
for(int i=1; i<=m; i++){
int x, y, z;
scanf("%d %d %d", &x, &y, &z);
edge[i] = Edge(x, y, z);
}
sort(edge+1, edge+m+1);
for(int i=0; i<k; i++){
scanf("%d %d", &ex[i], &ey[i]);
}
for(int i=1; i<=n; i++) scanf("%lld", &arr[i]);
}
vector<int> specialVec (1, -1);
int indices[100002];
int group[100002];
ll minWeight[42][42];
void contractGraph(){
dsu.init(n);
dsu2.init(n);
for(int i=0; i<k; i++){
dsu.merge(ex[i], ey[i]);
specialVec.push_back(ex[i]);
specialVec.push_back(ey[i]);
}
sort(specialVec.begin(), specialVec.end());
specialVec.erase(unique(specialVec.begin(), specialVec.end()), specialVec.end());
for(int i=1; i<(int)specialVec.size(); i++) indices[specialVec[i]] = i;
for(int i=1; i<=m; i++){
Edge e = edge[i];
if(dsu.find(e.x) == dsu.find(e.y)) continue;
dsu.merge(e.x, e.y);
dsu2.merge(e.x, e.y);
}
for(int i=1; i<=n; i++){
for(int j=1; j<(int)specialVec.size(); j++){
if(dsu2.find(i) == dsu2.find(specialVec[j])){
group[i] = j;
break;
}
}
assert(group[i]);
}
root = group[1];
vector<ll> tarr (arr, arr+n+1);
memset(arr, 0, sizeof(arr));
for(int i=1; i<=n; i++) arr[group[i]] += tarr[i];
n = (int)specialVec.size()-1;
assert(n<=k*2);
for(int i=1; i<=n; i++) for(int j=1; j<=n; j++) minWeight[i][j] = 1e18;
vector<Edge> edgeVec;
for(int i=1; i<=m; i++){
edge[i].x = group[edge[i].x], edge[i].y = group[edge[i].y];
if(edge[i].x == edge[i].y) continue;
if(edge[i].x > edge[i].y) swap(edge[i].x, edge[i].y);
minWeight[edge[i].x][edge[i].y] = min(minWeight[edge[i].x][edge[i].y], edge[i].z);
// edgeVec.push_back(Edge(edge[i].x, edge[i].y, edge[i].z));
}
for(int i=1; i<=n; i++) for(int j=1; j<=n; j++){
if(minWeight[i][j] > 1e17) continue;
edgeVec.push_back(Edge(i, j, minWeight[i][j]));
}
sort(edgeVec.begin(), edgeVec.end());
m = (int)edgeVec.size();
for(int i=1; i<=m; i++){
edge[i] = edgeVec[i-1];
}
for(int i=0; i<k; i++){
ex[i] = group[ex[i]], ey[i] = group[ey[i]];
assert(ex[i] != ey[i]);
st.insert(ll(ex[i])*1000000+ey[i]);
st.insert(ll(ey[i])*1000000+ex[i]);
}
}
ll calc(int x, int p=-1, ll sum=0){
ll ret = arr[x] * sum;
for(auto y: rLink[x]){
if(y.first == p) continue;
ret += calc(y.first, x, sum + ((st.find(ll(x)*1000000+y.first) != st.end()) ? y.second : 0));
}
return ret;
}
bool dfs(int x, int p, int goal, vector<int> &vec){
if(x==goal) return true;
for(auto y: nLink[x]){
if(y.first == p) continue;
vec.push_back(y.second);
if(dfs(y.first, x, goal, vec)) return true;
vec.pop_back();
}
for(auto y: rLink[x]){
if(y.first == p) continue;
if(dfs(y.first, x, goal, vec)) return true;
}
return false;
}
int main(){
input();
contractGraph();
for(int b=1; b<(1<<k); b++){ /// b: 선택된 추가 간선들의 집합
/// cycle detection
dsu2.init(n);
bool bad = 0;
for(int i=1; i<=n; i++) nLink[i].clear();
for(int i=0; i<k; i++){
if((b&(1<<i))==0) continue;
if(dsu2.find(ex[i]) == dsu2.find(ey[i])){
bad = 1;
break;
}
dsu2.merge(ex[i], ey[i]);
nLink[ex[i]].push_back(make_pair(ey[i], i));
nLink[ey[i]].push_back(make_pair(ex[i], i));
}
if(bad) continue;
dsu.init(n);
for(int i=1; i<=n; i++) rLink[i].clear();
for(int pnt=1; pnt<=m; pnt++){ /// 가장 가중치 작은 edge부터 시도해 보기
Edge e = edge[pnt];
if(dsu.find(e.x) == dsu.find(e.y)) continue;
ll w = e.z;
if(dsu2.find(e.x) != dsu2.find(e.y)){ /// 추가해도 되는 경우
rLink[e.x].push_back(make_pair(e.y, w));
rLink[e.y].push_back(make_pair(e.x, w));
dsu.merge(e.x, e.y);
dsu2.merge(e.x, e.y);
}
else{ /// 추가하면 안되는 경우
vector<int> delVec;
dfs(e.x, -1, e.y, delVec);
for(auto x: delVec){
nLink[ex[x]].erase(find(nLink[ex[x]].begin(), nLink[ex[x]].end(), make_pair(ey[x], x)));
nLink[ey[x]].erase(find(nLink[ey[x]].begin(), nLink[ey[x]].end(), make_pair(ex[x], x)));
rLink[ex[x]].push_back(make_pair(ey[x], w));
rLink[ey[x]].push_back(make_pair(ex[x], w));
dsu.merge(ex[x], ey[x]);
}
}
}
ans = max(ans, calc(root));
}
printf("%lld", ans);
}
Compilation message
toll.cpp: In function 'void input()':
toll.cpp:47:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
47 | scanf("%d %d %d", &n, &m, &k);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
toll.cpp:50:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
50 | scanf("%d %d %d", &x, &y, &z);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
toll.cpp:55:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
55 | scanf("%d %d", &ex[i], &ey[i]);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
toll.cpp:57:34: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
57 | for(int i=1; i<=n; i++) scanf("%lld", &arr[i]);
| ~~~~~^~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
5716 KB |
Output is correct |
| 2 |
Correct |
3 ms |
5716 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
5716 KB |
Output is correct |
| 2 |
Correct |
3 ms |
5716 KB |
Output is correct |
| 3 |
Correct |
5 ms |
5716 KB |
Output is correct |
| 4 |
Correct |
5 ms |
5820 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
5716 KB |
Output is correct |
| 2 |
Correct |
3 ms |
5716 KB |
Output is correct |
| 3 |
Correct |
5 ms |
5716 KB |
Output is correct |
| 4 |
Correct |
5 ms |
5820 KB |
Output is correct |
| 5 |
Correct |
6 ms |
5844 KB |
Output is correct |
| 6 |
Correct |
6 ms |
5844 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
5716 KB |
Output is correct |
| 2 |
Correct |
3 ms |
5716 KB |
Output is correct |
| 3 |
Correct |
5 ms |
5716 KB |
Output is correct |
| 4 |
Correct |
5 ms |
5820 KB |
Output is correct |
| 5 |
Correct |
6 ms |
5844 KB |
Output is correct |
| 6 |
Correct |
6 ms |
5844 KB |
Output is correct |
| 7 |
Correct |
190 ms |
12508 KB |
Output is correct |
| 8 |
Correct |
219 ms |
12580 KB |
Output is correct |
| 9 |
Correct |
214 ms |
12492 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
5716 KB |
Output is correct |
| 2 |
Correct |
3 ms |
5716 KB |
Output is correct |
| 3 |
Correct |
5 ms |
5716 KB |
Output is correct |
| 4 |
Correct |
5 ms |
5820 KB |
Output is correct |
| 5 |
Correct |
6 ms |
5844 KB |
Output is correct |
| 6 |
Correct |
6 ms |
5844 KB |
Output is correct |
| 7 |
Correct |
190 ms |
12508 KB |
Output is correct |
| 8 |
Correct |
219 ms |
12580 KB |
Output is correct |
| 9 |
Correct |
214 ms |
12492 KB |
Output is correct |
| 10 |
Correct |
2452 ms |
12520 KB |
Output is correct |
| 11 |
Execution timed out |
2582 ms |
12540 KB |
Time limit exceeded |
| 12 |
Halted |
0 ms |
0 KB |
- |
