| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 159326 |
2019-10-22T11:07:27 Z |
EntityIT |
Toll (APIO13_toll) |
C++14 |
|
282 ms |
7656 KB |
#include<bits/stdc++.h>
using namespace std;
using LL = long long;
int n, nRoad, nNewRoad, curTime;
LL ans;
vector<int> nPeople, newId, nP, par, be;
struct Edge { int u, v, c; };
vector<Edge> road;
vector<pair<int, int> > newRoad;
vector<vector<pair<int, int> > > gr;
struct Dsu {
vector<int> pSet;
Dsu(int nV) {
pSet.assign(nV + 5, 0);
iota(pSet.begin(), pSet.end(), 0);
}
void reset(int nV) {
pSet.assign(nV + 5, 0);
iota(pSet.begin(), pSet.end(), 0);
}
int findSet(int i) { return i == pSet[i] ? i : pSet[i] = findSet(pSet[i]); }
bool sameSet(int i, int j) { return findSet(i) == findSet(j); }
void unionSet(int i, int j) {
i = findSet(i); j = findSet(j);
if (i == j) return ;
pSet[i] = j;
}
};
int getBit(int a, int bit) { return (a >> bit) & 1; }
void dfs(int u, int p) {
be[u] = ++curTime;
par[u] = p;
for (auto pai : gr[u]) {
int v = pai.first;
if (v == p) continue ;
dfs(v, u);
}
}
LL calc(int u, int p, LL& ret) {
LL cnt = nP[u];
for (auto pai : gr[u]) {
int v = pai.first;
if (v == p) continue ;
cnt += calc(v, u, ret);
}
for (auto pai : gr[u]) {
int v = pai.first, c = pai.second;
if (v != p) continue ;
if (c < 0) ret += -c * cnt;
}
return cnt;
}
int main() {
// freopen("input", "r", stdin);
scanf(" %d %d %d", &n, &nRoad, &nNewRoad);
road.assign(nRoad, {} );
for (int i = 0; i < nRoad; ++i) {
int u, v, c; scanf(" %d %d %d", &u, &v, &c);
road[i] = { u, v, c };
}
sort(road.begin(), road.end(), [](Edge i, Edge j) { return i.c < j.c; } );
newRoad.assign(nNewRoad, {} );
for (int i = 0; i < nNewRoad; ++i) {
int u, v; scanf(" %d %d", &u, &v);
newRoad[i] = { u, v };
}
nPeople.assign(n + 5, 0);
for (int i = 1; i <= n; ++i) scanf(" %d", &nPeople[i]);
Dsu dsu(n), dsu2(n);
for (auto aNewRoad : newRoad) dsu2.unionSet(aNewRoad.first, aNewRoad.second);
for (auto aRoad : road) {
int u = aRoad.u, v = aRoad.v;
if (!dsu2.sameSet(u, v) ) {
dsu2.unionSet(u, v);
dsu.unionSet(u, v);
}
}
newId.assign(n + 5, 0);
int iId = 0;
for (int i = 1; i <= n; ++i) {
if (!newId[dsu.findSet(i)]) newId[dsu.findSet(i)] = ++iId;
}
vector<Edge> staredRoad;
set<pair<int, int> > addedRoad;
for (auto aRoad : road) {
int u = aRoad.u, v = aRoad.v, c = aRoad.c;
u = newId[dsu.findSet(u)];
v = newId[dsu.findSet(v)];
if (u != v && !addedRoad.count(pair<int, int>{ u, v } ) ) {
staredRoad.push_back( { u, v, c } );
addedRoad.insert( { u, v } );
}
}
for (auto &aNewRoad : newRoad) {
aNewRoad.first = newId[dsu.findSet(aNewRoad.first)];
aNewRoad.second = newId[dsu.findSet(aNewRoad.second)];
}
nP.assign(n + 5, 0);
for (int i = 1; i <= n; ++i) nP[ newId[dsu.findSet(i)] ] += nPeople[i];
for (int mask = 0; mask < (1 << nNewRoad); ++mask) {
bool valid = 1;
Dsu check(iId);
gr.assign(iId + 5, vector<pair<int, int> >() );
for (int i = 0; i < nNewRoad; ++i) if (getBit(mask, i) ) {
int u = newRoad[i].first, v = newRoad[i].second;
if (check.sameSet(u, v) ) {
valid = 0;
break ;
}
check.unionSet(u, v);
gr[u].push_back( { v, 0 } );
gr[v].push_back( { u, 0 } );
}
if (!valid) continue ;
for (auto aRoad : staredRoad) {
int u = aRoad.u, v = aRoad.v, c = aRoad.c;
if (check.sameSet(u, v) ) continue ;
check.unionSet(u, v);
gr[u].push_back( { v, c } );
gr[v].push_back( { u, c } );
}
par.assign(iId + 5, 0);
be.assign(iId + 5, 0); curTime = 0;
dfs(1, 0);
dsu.reset(iId);
for (auto aRoad : staredRoad) {
int u = aRoad.u, v = aRoad.v, c = aRoad.c;
while (u != v) {
if (be[u] < be[v]) swap(u, v);
for (auto &pai : gr[u]) {
int nxt = pai.first, cost = pai.second;
if (nxt != par[u]) continue ;
if (!cost) pai.second = -c;
dsu.unionSet(u, par[u]);
u = dsu.findSet(u);
}
}
}
LL ret = 0;
calc(1, 0, ret);
ans = max(ans, ret);
}
printf("%lld", ans);
return 0;
}
Compilation message
toll.cpp: In function 'int main()':
toll.cpp:64:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf(" %d %d %d", &n, &nRoad, &nNewRoad);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
toll.cpp:68:27: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
int u, v, c; scanf(" %d %d %d", &u, &v, &c);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
toll.cpp:75:24: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
int u, v; scanf(" %d %d", &u, &v);
~~~~~^~~~~~~~~~~~~~~~~~
toll.cpp:80:39: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
for (int i = 1; i <= n; ++i) scanf(" %d", &nPeople[i]);
~~~~~^~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
256 KB |
Output is correct |
| 2 |
Correct |
2 ms |
376 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
256 KB |
Output is correct |
| 2 |
Correct |
2 ms |
376 KB |
Output is correct |
| 3 |
Correct |
5 ms |
256 KB |
Output is correct |
| 4 |
Correct |
4 ms |
376 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
256 KB |
Output is correct |
| 2 |
Correct |
2 ms |
376 KB |
Output is correct |
| 3 |
Correct |
5 ms |
256 KB |
Output is correct |
| 4 |
Correct |
4 ms |
376 KB |
Output is correct |
| 5 |
Correct |
7 ms |
504 KB |
Output is correct |
| 6 |
Correct |
7 ms |
504 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
256 KB |
Output is correct |
| 2 |
Correct |
2 ms |
376 KB |
Output is correct |
| 3 |
Correct |
5 ms |
256 KB |
Output is correct |
| 4 |
Correct |
4 ms |
376 KB |
Output is correct |
| 5 |
Correct |
7 ms |
504 KB |
Output is correct |
| 6 |
Correct |
7 ms |
504 KB |
Output is correct |
| 7 |
Incorrect |
282 ms |
7656 KB |
Output isn't correct |
| 8 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
256 KB |
Output is correct |
| 2 |
Correct |
2 ms |
376 KB |
Output is correct |
| 3 |
Correct |
5 ms |
256 KB |
Output is correct |
| 4 |
Correct |
4 ms |
376 KB |
Output is correct |
| 5 |
Correct |
7 ms |
504 KB |
Output is correct |
| 6 |
Correct |
7 ms |
504 KB |
Output is correct |
| 7 |
Incorrect |
282 ms |
7656 KB |
Output isn't correct |
| 8 |
Halted |
0 ms |
0 KB |
- |
