| # |
제출 시각 |
아이디 |
문제 |
언어 |
결과 |
실행 시간 |
메모리 |
| 122382 |
2019-06-28T06:36:24 Z |
윤교준(#2990) |
통행료 (APIO13_toll) |
C++14 |
|
5 ms |
3200 KB |
#include <bits/stdc++.h>
#define eb emplace_back
#define sz(V) ((int)(V).size())
#define allv(V) ((V).begin()),((V).end())
#define sorv(V) sort(allv(V))
#define univ(V) (V).erase(unique(allv(V)),(V).end())
#define upmax(a,b) (a)=max((a),(b))
#define upmin(a,b) (a)=min((a),(b))
#define INF (0x3f3f3f3f)
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const bool debug = 0;
const int MAXN = 100055;
const int MAXK = 25;
struct DJF {
DJF() { init(); }
int ud[MAXN];
void init() { iota(ud, ud+MAXN, 0); }
int uf(int i) { return i == ud[i] ? i : (ud[i] = uf(ud[i])); }
void uf(int a, int b) { ud[uf(b)] = uf(a); }
} djf;
struct EDG {
EDG(int p, int v, ll sumU, ll sumD, int mxe, int mne)
: p(p), v(v), sumU(sumU), sumD(sumD), mxe(mxe), mne(mne), ign(false) {}
EDG(int p, int v) : p(p), v(v), ign(true) {}
EDG() : ign(false) {}
int p, v;
ll sumU, sumD;
int mxe, mne;
bool ign;
int nxt(int i) { return p^v^i; }
ll sums() { return sumU + sumD; }
void swp() { swap(p, v); swap(sumU, sumD); }
void prt() {
printf("EDG : p=%d, v=%d, sumU=%lld, sumD=%lld, mxe=%d, mne=%d, ign=%d\n", p, v, sumU, sumD, mxe, mne, int(ign));
}
};
struct GPH {
GPH() : edgn(0) {
memset(D, 0, MAXK<<5);
memset(prte, 0, MAXK<<4);
}
vector<int> G[MAXK<<2];
EDG edg[MAXK<<2]; int edgn;
set<int> PQ[MAXK<<2];
ll D[MAXK<<2];
int prte[MAXK<<2];
void prt() {
puts("GRAPH");
printf("edgn = %d\n", edgn);
for(int i = 1; i <= edgn; i++) {
printf("EDG %d : ", i);
edg[i].prt();
}
for(int i = 1; i < (MAXK<<2); i++) if(!G[i].empty()) {
printf("G %d : ", i);
for(int v : G[i]) printf("%d ", v);
puts("");
}
for(int i = 1; i < (MAXK<<2); i++) if(D[i])
printf("D %d ; %lld\n", i, D[i]);
for(int i = 1; i < (MAXK<<2); i++) if(prte[i])
printf("prte %d ; %d\n", i, prte[i]);
puts("GRAPHEND");
}
bitset<MAXK<<2> chk;
int lca(int a, int b) {
if(a == b) return a;
chk.reset();
for(;;) {
chk[a] = true;
if(1 == a) break;
a = edg[prte[a]].p;
}
for(;;) {
if(chk[b]) return b;
b = edg[prte[b]].p;
}
}
void dfs(int i, int p) {
for(int e : G[i]) {
int v = edg[e].nxt(i);
if(v == p) {
prte[i] = e;
continue;
}
if(edg[e].p != i) edg[e].swp();
dfs(v, i);
}
}
void dfssum(int i) {
auto &V = PQ[i];
for(int e : G[i]) {
int v = edg[e].v;
if(v == i) continue;
dfssum(v);
D[i] += D[v];
if(!edg[e].ign) D[i] += edg[e].sums();
auto &T = PQ[v];
if(edg[e].ign) edg[e].mxe = *T.begin();
for(int w : T) {
auto it = V.find(w);
if(V.end() == it) V.insert(w);
else V.erase(it);
}
T.clear();
}
}
void remove(int v, int e) {
G[v].erase(find(allv(G[v]), e));
}
void goupWithEdge(int a, int c, int &mxe, int &mxei) {
for(int v = a, e; v != c;) {
e = prte[v];
if(!edg[e].ign && mxe < edg[e].mxe) {
mxe = edg[e].mxe;
mxei = e;
}
v = edg[e].p;
}
}
bool addEdge(int a, int b) {
int c = lca(a, b);
int mxe = -1, mxei = -1;
goupWithEdge(a, c, mxe, mxei);
goupWithEdge(b, c, mxe, mxei);
if(mxei < 0) return false;
D[edg[mxei].p] += edg[mxei].sumU;
D[edg[mxei].v] += edg[mxei].sumD;
remove(edg[mxei].p, mxei);
remove(edg[mxei].v, mxei);
edgn++;
edg[edgn] = EDG(a, b);
G[a].eb(edgn);
G[b].eb(edgn);
dfs(1, -1);
return true;
}
void addEdge(EDG e) {
edgn++;
edg[edgn] = e;
G[e.p].eb(edgn);
G[e.v].eb(edgn);
}
ll getAns(int n) {
for(int i = 1; i < n; i++) {
PQ[edg[i].p].insert(edg[i].mne);
PQ[edg[i].v].insert(edg[i].mne);
}
dfssum(1);
ll ret = 0;
for(int i = n; i <= edgn; i++) if(edg[i].ign) {
ret += D[edg[i].v] * edg[i].mxe;
if(debug) {
printf("GETANS EDG : %d %d / %lld %d\n", edg[i].p, edg[i].v, D[edg[i].v], edg[i].mxe);
}
}
return ret;
}
};
vector<int> G[MAXN];
vector<int> TV;
vector<pii> TE;
vector<EDG> EDGV;
bitset<MAXN> chkV, chkE;
int prt[17][MAXN];
int prte[MAXN], dep[MAXN], cnt[MAXN], dfo[MAXN];
int A[MAXN], B[MAXN], C[MAXN];
ll D[MAXN];
int E[MAXK], F[MAXK];
ll Ans;
int N, K;
int getI(int v) { return int(lower_bound(allv(TV), v) - TV.begin()) + 1; }
bitset<1<<MAXK> solveDFSchk;
void solveDFS(GPH &gph, int key) {
solveDFSchk[key] = true;
for(int i = 0; i < K; i++) {
if((key & (1<<i)) || solveDFSchk[key | (1<<i)]) continue;
GPH nxt = gph;
nxt.addEdge(getI(E[i]), getI(F[i]));
solveDFS(nxt, key | (1<<i));
}
if(debug) {
printf("============ solveDFS %d\n", key);
gph.prt();
ll t = gph.getAns(sz(TV));
printf("Ans = %lld\n\n", t);
upmax(Ans, t);
} else {
upmax(Ans, gph.getAns(sz(TV)));
}
}
void solve() {
GPH tree;
for(auto e : EDGV) {
e.p = getI(e.p);
e.v = getI(e.v);
tree.addEdge(e);
}
for(int v : TV) tree.D[getI(v)] = D[v];
tree.dfs(1, -1);
if(debug) {
tree.prt();
}
solveDFS(tree, 0);
}
bool isin(int p, int v) { return dfo[p] <= dfo[v] && dfo[v] < dfo[p] + cnt[p]; }
int lca(int a, int b) {
if(dep[a] > dep[b]) swap(a, b);
const int dt = dep[b] - dep[a];
for(int i = 17; i--;) if(dt & (1<<i))
b = prt[i][b];
if(a == b) return a;
for(int i = 17; i--;) if(prt[i][a] != prt[i][b]) {
a = prt[i][a];
b = prt[i][b];
}
return prt[0][a];
}
void dfs(int i, int &c) {
cnt[i] = 1; dfo[i] = ++c;
for(int e : G[i]) {
int v = A[e]^B[e]^i;
if(dep[v]) continue;
dep[v] = dep[i] + 1;
prte[v] = e;
prt[0][v] = i;
dfs(v, c);
cnt[i] += cnt[v];
}
}
void input() {
ios::sync_with_stdio(false);
vector<pair<int, pii>> EV;
int M;
cin >> N >> M >> K;
for(int i = 0, a, b, c; i < M; i++) {
cin >> a >> b >> c;
EV.eb(c, pii(a, b));
}
for(int i = 0; i < K; i++) cin >> E[i] >> F[i];
for(int i = 1; i <= N; i++) cin >> D[i];
sorv(EV); M = 0;
for(auto &e : EV) {
int a, b, c = e.first;
tie(a, b) = e.second;
if(djf.uf(a) == djf.uf(b)) continue;
djf.uf(a, b);
M++;
A[M] = a; B[M] = b; C[M] = c;
G[a].eb(M);
G[b].eb(M);
}
}
void treeCompress() {
vector<int> V, VT;
V.eb(1);
for(int i = 0; i < K; i++) {
V.eb(E[i]);
V.eb(F[i]);
}
sort(allv(V), [&](int a, int b) { return dfo[a] < dfo[b]; });
univ(V);
for(int i = 1, n = sz(V); i < n; i++)
V.eb(lca(V[i-1], V[i]));
sort(allv(V), [&](int a, int b) { return dfo[a] < dfo[b]; });
univ(V);
for(int v : V) chkV[v] = true;
TV = V; sorv(TV);
for(int v : V) {
for(; !VT.empty() && !isin(VT.back(), v); VT.pop_back());
if(!VT.empty()) TE.eb(VT.back(), v);
VT.eb(v);
}
}
void colorEdges() {
for(auto &e : TE) {
int p, v; tie(p, v) = e;
for(; v != p;) {
chkE[prte[v]] = true;
v = prt[0][v];
}
}
}
void dfsleaf(int i) {
for(int e : G[i]) if(e != prte[i]) {
int v = A[e]^B[e]^i;
dfsleaf(v);
if(chkE[e]) continue;
D[i] += D[v];
D[v] = 0;
}
}
void makeEdges() {
for(auto &ed : TE) {
int p, v; tie(p, v) = ed;
ll sumU = 0, sumD = 0;
int mxe = -1, mne = INF;
for(int e; v != p;) {
e = prte[v];
upmax(mxe, C[e]);
if(C[e] < mne) {
mne = C[e];
sumD += sumU;
sumU = 0;
}
v = prt[0][v];
sumU += D[v];
}
sumU -= D[p];
EDGV.eb(p, ed.second, sumU, sumD, mxe, mne);
}
}
int main() {
input();
if(debug) {
for(int i = 1; i < N; i++) printf("EDG %d ; %d %d %d\n", i, A[i], B[i], C[i]);
}
dep[1] = 1; { int c = 0; dfs(1, c); }
for(int j = 1; j < 17; j++) for(int i = 1; i <= N; i++)
prt[j][i] = prt[j-1][prt[j-1][i]];
if(debug) {
puts("DFS");
for(int i = 1; i <= N; i++)
printf("%d ; %d %d / %d %d %d\n", i, prt[0][i], prte[i], dep[i], cnt[i], dfo[i]);
}
treeCompress();
colorEdges();
dfsleaf(1);
makeEdges();
if(debug) {
for(int i = 1; i <= N; i++)
printf("D %d ; %lld\n", i, D[i]);
printf("TV :: ");
for(int v : TV) printf("%d ", v);
puts("");
printf("%d edges\n", sz(EDGV));
for(auto &e : EDGV) {
e.prt();
}
}
solve();
cout << Ans << endl;
return 0;
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
5 ms |
3200 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
5 ms |
3200 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
5 ms |
3200 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
5 ms |
3200 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
5 ms |
3200 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
