| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 122423 |
2019-06-28T07:43:05 Z |
윤교준(#2990) |
Toll (APIO13_toll) |
C++14 |
|
7 ms |
7168 KB |
#include <bits/stdc++.h>
#define rf(x) (x)=0;while(*p<48)p++;while(47<*p)(x)=((x)<<3)+((x)<<1)+(*p++&15);
#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;
unsigned char str[10000055], *p=str;
const bool debug = 0;
const int MAXN = 100055;
const int MAXK = 21;
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)
: p(p), v(v), sumU(sumU), sumD(sumD), mxe(mxe), ign(false), dead(false) {}
EDG(int p, int v) : p(p), v(v), ign(true), dead(false) {}
EDG() : ign(false) {}
int p, v;
ll sumU, sumD;
int mxe;
bool ign, dead;
int nxt(int i) { return p^v^i; }
ll sums() { return sumU + sumD; }
void swp() { swap(p, v); swap(sumU, sumD); }
};
struct GPH {
GPH() : edgn(0), SWPVn(0) {}
pii PRTEV[500055]; int PRTEVn;
int SWPV[500055], SWPVn;
vector<int> G[MAXK<<2];
EDG edg[MAXK*5]; int edgn;
set<int> PQ[MAXK<<2];
ll D[MAXK<<2], E[MAXK<<2];
int prte[MAXK<<2];
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]) if(!edg[e].dead) {
int v = edg[e].nxt(i);
if(v == p) {
PRTEV[PRTEVn++] = pii(i, prte[i]);
prte[i] = e;
continue;
}
if(edg[e].p != i) {
edg[e].swp();
SWPV[SWPVn++] = e;
}
dfs(v, i);
}
}
void dfssum(int i, int p) {
auto &V = PQ[i];
E[i] = D[i];
for(int e : G[i]) if(!edg[e].dead) {
int v = edg[e].nxt(i);
if(v == p) {
PRTEV[PRTEVn++] = pii(i, prte[i]);
prte[i] = e;
continue;
}
if(edg[e].p != i) {
edg[e].swp();
SWPV[SWPVn++] = e;
}
dfssum(v, i);
E[i] += E[v];
if(!edg[e].ign) E[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;
}
}
int 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 -1;
D[edg[mxei].p] += edg[mxei].sumU;
D[edg[mxei].v] += edg[mxei].sumD;
edg[mxei].dead = true;
//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 mxei;
}
void rollback(int mxei, int a, int b) {
G[a].pop_back();
G[b].pop_back();
edgn--;
edg[mxei].dead = false;
D[edg[mxei].p] -= edg[mxei].sumU;
D[edg[mxei].v] -= edg[mxei].sumD;
}
void rollbackSWP(int vn) {
for(; vn < SWPVn;) {
SWPVn--;
edg[SWPV[SWPVn]].swp();
}
}
void rollbackPRTE(int vn) {
for(int a, b; vn < PRTEVn;) {
PRTEVn--;
tie(a, b) = PRTEV[PRTEVn];
prte[a] = b;
}
}
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[i].clear();
for(int i = 1; i < n; i++) if(edg[i].dead) {
PQ[edg[i].p].insert(edg[i].mxe);
PQ[edg[i].v].insert(edg[i].mxe);
}
dfssum(1, -1);
ll ret = 0;
for(int i = n; i <= edgn; i++) if(edg[i].ign)
ret += E[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;
int tn = gph.SWPVn, ten = gph.PRTEVn;
if(0 == rand()%10) upmax(Ans, gph.getAns(sz(TV)));
for(int i = 0; i < K; i++) {
if((key & (1<<i)) || solveDFSchk[key | (1<<i)]) continue;
//gph.dfs(1, -1);
int vn = gph.SWPVn, pen = gph.PRTEVn;
int ret = gph.addEdge(getI(E[i]), getI(F[i]));
if(ret < 0) continue;
solveDFS(gph, key | (1<<i));
gph.rollback(ret, getI(E[i]), getI(F[i]));
gph.rollbackSWP(vn);
gph.rollbackPRTE(pen);
}
gph.rollbackSWP(tn);
gph.rollbackPRTE(ten);
}
GPH tree;
void solve() {
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);
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() {
fread(str, 1, 10000055, stdin);
vector<pair<int, pii>> EV;
int M;
rf(N) rf(M) rf(K)
for(int i = 0, a, b, c; i < M; i++) {
rf(a) rf(b) rf(c)
EV.eb(c, pii(a, b));
}
for(int i = 0; i < K; i++) { rf(E[i]) rf(F[i]) }
for(int i = 1; i <= N; i++) { rf(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;
for(int e; v != p;) {
e = prte[v];
if(mxe < C[e]) {
mxe = C[e];
sumD += sumU;
sumU = 0;
}
v = prt[0][v];
sumU += D[v];
}
sumU -= D[p];
EDGV.eb(p, ed.second, sumU, sumD, mxe);
}
}
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]];
treeCompress();
colorEdges();
dfsleaf(1);
makeEdges();
solve();
cout << Ans << endl;
return 0;
}
Compilation message
toll.cpp: In constructor 'GPH::GPH()':
toll.cpp:55:23: warning: 'GPH::edgn' will be initialized after [-Wreorder]
EDG edg[MAXK*5]; int edgn;
^~~~
toll.cpp:52:20: warning: 'int GPH::SWPVn' [-Wreorder]
int SWPV[500055], SWPVn;
^~~~~
toll.cpp:49:2: warning: when initialized here [-Wreorder]
GPH() : edgn(0), SWPVn(0) {}
^~~
toll.cpp: In function 'void input()':
toll.cpp:287:7: warning: ignoring return value of 'size_t fread(void*, size_t, size_t, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
fread(str, 1, 10000055, stdin);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
7168 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
7168 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
7168 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
7168 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
7168 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
