| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 512626 |
2022-01-16T14:32:07 Z |
blue |
Training (IOI07_training) |
C++17 |
|
42 ms |
1588 KB |
#include <iostream>
#include <cassert>
#include <vector>
#include <algorithm>
using namespace std;
const int maxN = 1'000;
const int logN = 10;
using vi = vector<int>;
using pii = pair<int, int>;
using vvi = vector<vi>;
#define sz(x) int(x.size())
struct trail
{
int a;
int b;
int c;
};
int N, M;
vector<trail> trails;
vi edge[1+maxN];
vi par(1+maxN, 0);
vvi anc(1+maxN, vi(1+logN, 0));
vector< vector< vi > > desc(1+maxN, vector<vi>(1+logN));
vi depth(1+maxN, 0);
void dfs(int u)
{
for(int v: edge[u])
{
if(v == par[u]) continue;
par[v] = u;
depth[v] = 1 + depth[u];
dfs(v);
}
}
int ancestor(int u, int k)
{
// cerr << "ancestor " << u << ' ' << k << "\n";
for(int e = 0; e <= logN; e++)
if(k & (1 << e))
u = anc[u][e];
return u;
}
int lca(int u, int v)
{
if(depth[u] > depth[v]) swap(u, v);
v = ancestor(v, depth[v] - depth[u]);
if(u == v) return u;
for(int e = logN; e >= 0; e--)
{
if(anc[u][e] == anc[v][e]) continue;
u = anc[u][e];
v = anc[v][e];
}
return anc[u][0];
}
struct vtrail
{
int v;
int c;
};
vector<vtrail> v_trails[1+maxN];
vector<trail> h_trails[1+maxN];
int basicCost = 0;
int defaultCost = 0;
vi strict(1+maxN, 0);
vi loose(1+maxN, 0);
vvi loose_lift(1+maxN, vi(1+logN, 0));
vi child_loose_sum(1+maxN, 0);
vvi dp(1+maxN);
int loose_query(int u, int k)
{
int ans = 0;
for(int e = 0; e <= logN; e++)
{
if(k & (1 << e))
{
ans += loose_lift[u][e];
u = anc[u][e];
}
}
// cerr << "loose query " << u << ' ' << k <<
return ans;
}
void binary_lift(int u, int e)
{
loose_lift[u][e] = loose_lift[anc[u][e-1]][e-1] + loose_lift[u][e-1];
// cerr << "computing loose_lift " << u << " " << e << " as " << loose_lift[u][e] << '\n';
for(int v: desc[u][e])
binary_lift(v, e+1);
}
vi inv_pow(2000);
// vi dp;
vi child_ind(1+maxN);
void final_dfs(int u)
{
// int << "enter final dfs " << u << '\n';
for(int v: desc[u][0])
{
final_dfs(v);
child_loose_sum[u] += loose[v];
}
// for(int v: desc[u][0])
// {
// loose_lift[v][0] = child_loose_sum[u] - loose[v];
// for(int v2: desc[v][0])
// binary_lift(v2, 1);
// }
// cerr << "\n\n\n\n entering computations of " << u << '\n';
//somehow compute strict
// cerr << "A\n";
// cerr << "\n\n\n\n\n";
int z = sz(desc[u][0]);
if(z > 0)
{
dp[u] = vi((1<<z), 0);
for(int i = 0; i < z; i++)
child_ind[desc[u][0][i]] = i;
// for(int i = 0; i < z; i++) //IS THIS A GOOD IDEA?
// {
// int v = desc[u][0][i];
// loose_lift[v][0] = dp[u][(1<<z) - 1 - (1<<i)];
//
// cerr << "loose lift " << v << ' ' << 0 << " = " << loose_lift[v][0] << '\n';
//
// for(int v2: desc[v][0])
// binary_lift(v2, 1);
// }
// cerr << "u\n";
vi trail_occ[z];
int tz = sz(h_trails[u]);
// cerr << "tz = " << tz << '\n';
vi lc(tz), rc(tz);
for(int i = 0; i < tz; i++)
{
// cerr << "i = " << i << '\n';
// cerr << "val = " << h_trails[u][i].a << '\n';
// cerr << "?\n";
lc[i] = child_ind[ancestor(h_trails[u][i].a, depth[h_trails[u][i].a] - depth[u] - 1)];
// cerr << "#\n";
rc[i] = child_ind[ancestor(h_trails[u][i].b, depth[h_trails[u][i].b] - depth[u] - 1)];
// cerr << "lc rc computed\n";
if(lc[i] > rc[i]) swap(lc[i], rc[i]);
trail_occ[lc[i]].push_back(i);
trail_occ[rc[i]].push_back(i);
// trail_occ[rc[i]].push_back(i);
// cerr << "h trail = " << h_trails[u][i].a << ' ' << h_trails[u][i].b << ' ' << h_trails[u][i].c << '\n';
}
// cerr << "v\n";
dp[u][0] = 0;
for(int mask = 1; mask < (1<<z); mask++)
{
// cerr << "###\n";
// cerr << "desc mask = " << mask << '\n';
if(mask == (mask & -mask))
{
// cerr << "case 1\n";
// cerr << inv_pow[mask] << " - " << desc[u][0][inv_pow[mask]] << " : " << loose[desc[u][0][inv_pow[mask]]] << '\n';
dp[u][mask] = loose[ desc[u][0][ inv_pow[mask] ] ];
// if(u == 1)
// {
// cerr << "at root: " << "mask " << mask << " = " << dp[u][mask] << '\n';
// }
}
else
{
// cerr << "case 2\n";
int lb = inv_pow[mask & -mask];
dp[u][mask] = dp[u][mask - (mask&-mask)] + loose[ desc[u][0][lb] ];
// if(u == 1)
// {
// cerr << "at root: " << "mask " << mask << " = " << dp[u][mask] << '\n';
// }
// cerr << "lb = " << lb << " : " << sz(trail_occ[lb]) << '\n';
for(int ti: trail_occ[lb])
{
if(!(mask & (1 << rc[ti]))) continue;
if(!(mask & (1 << lc[ti]))) continue;
// assert(mask & (1 << lc[ti]));
// cerr << "\n\n";
// cerr << "checking trail\n";
// cerr << "checking trail : " << h_trails[u][ti].a << ' ' << h_trails[u][ti].b << ' ' << h_trails[u][ti].c << '\n';
int newval = dp[u][mask - (1<<lc[ti]) - (1<<rc[ti])];
int a = h_trails[u][ti].a;
int b = h_trails[u][ti].b;
int c = h_trails[u][ti].c;
if(u == 1)
{
// cerr << "at root: " << "checking trail " << a << ' ' << b << ' ' << c << '\n';
// cerr << lc[ti] << ' ' << rc[ti] << '\n';
// cerr << "current mask = " << mask << "\n";
// cerr << a << " : ll = " << loose_lift[a][0] << ' ' << depth[a] - depth[u] - 1 << '\n';
// cerr << newval << ' ' << strict[a] + loose_query(a, depth[a] - depth[u] - 1) << ' ' << strict[b] + loose_query(b, depth[b] - depth[u] - 1) << ' ' << c << '\n';
// cerr << "\n\n\n";
}
newval += strict[a] + loose_query(a, depth[a] - depth[u] - 1);
newval += strict[b] + loose_query(b, depth[b] - depth[u] - 1);
newval += c;
dp[u][mask] = max(dp[u][mask], newval);
}
}
}
strict[u] = dp[u][(1<<z) - 1];
// if(u == 1)
// {
// // cerr << "dfs reached root = " << u << '\n';
// // cerr << "children: ";
// // for(int v: desc[u][0]) cerr << v << ' ';
// // cerr << '\n';
//
// for(int mask = 0; mask < (1<<z); mask++) cerr << mask << " : " << dp[u][mask] << '\n';
// }
//
for(int i = 0; i < z; i++)
{
int v = desc[u][0][i];
loose_lift[v][0] = dp[u][(1<<z) - 1 - (1<<i)];
// cerr << "loose lift " << v << ' ' << 0 << " = " << loose_lift[v][0] << '\n';
for(int v2: desc[v][0])
binary_lift(v2, 1);
}
}
// cerr << "B\n";
// cerr << "\n\n\n";
loose[u] = strict[u];
for(vtrail vt: v_trails[u])
{
// cerr << "vt = " << u << " : " << vt.v << ' ' << vt.c << '\n';
loose[u] = max(loose[u], loose_query(vt.v, depth[vt.v] - depth[u]) + strict[vt.v] + vt.c);
}
// cerr << "\n\n\n";
// cerr << "u = " << u << " : " << "strict, loose = " << strict[u] << ' ' << loose[u] << '\n';
// cerr << "exit final dfs " << u << '\n';
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin >> N >> M;
for(int e = 1; e <= M; e++)
{
int a, b;
int c;
cin >> a >> b >> c;
if(c != 0) trails.push_back({a, b, c});
else
{
edge[a].push_back(b);
edge[b].push_back(a);
}
}
dfs(1);
for(int i = 1; i <= N; i++) anc[i][0] = par[i];
for(int e = 1; e <= logN; e++)
for(int i = 0; i <= N; i++)
anc[i][e] = anc[ anc[i][e-1] ][e-1];
for(int i = 0; i <= N; i++)
for(int e = 0; e <= logN; e++)
if(anc[i][e] != 0)
desc[anc[i][e]][e].push_back(i);
for(auto& t: trails)
{
if(depth[t.a] % 2 != depth[t.b] % 2)
{
basicCost += t.c;
continue;
}
defaultCost += t.c;
int l = lca(t.a, t.b);
// cerr << t.a << ' ' << t.b << ' ' << t.c << " : root = " << l << '\n';
if(l == t.a)
{
v_trails[ancestor(t.b, depth[t.b] - depth[t.a] - 1)].push_back({t.b, t.c});
}
else if(l == t.b)
{
v_trails[ancestor(t.a, depth[t.a] - depth[t.b] - 1)].push_back({t.a, t.c});
}
else h_trails[l].push_back(t);
}
for(int e = 0; e < 10; e++)
inv_pow[(1<<e)] = e;
// cerr << "A\n";
final_dfs(1);
cout << basicCost + (defaultCost - strict[1]) << '\n';
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
844 KB |
Output is correct |
| 2 |
Correct |
1 ms |
844 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
844 KB |
Output is correct |
| 2 |
Correct |
1 ms |
844 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
1484 KB |
Output is correct |
| 2 |
Correct |
3 ms |
1484 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
844 KB |
Output is correct |
| 2 |
Correct |
1 ms |
900 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
844 KB |
Output is correct |
| 2 |
Correct |
1 ms |
900 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
844 KB |
Output is correct |
| 2 |
Correct |
1 ms |
844 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
844 KB |
Output is correct |
| 2 |
Correct |
1 ms |
844 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
972 KB |
Output is correct |
| 2 |
Correct |
2 ms |
972 KB |
Output is correct |
| 3 |
Correct |
6 ms |
972 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
1100 KB |
Output is correct |
| 2 |
Correct |
12 ms |
1220 KB |
Output is correct |
| 3 |
Correct |
4 ms |
1164 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
1116 KB |
Output is correct |
| 2 |
Correct |
2 ms |
1100 KB |
Output is correct |
| 3 |
Correct |
42 ms |
1588 KB |
Output is correct |
| 4 |
Correct |
2 ms |
1036 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
1228 KB |
Output is correct |
| 2 |
Correct |
5 ms |
1564 KB |
Output is correct |
| 3 |
Correct |
6 ms |
1240 KB |
Output is correct |
| 4 |
Correct |
8 ms |
1168 KB |
Output is correct |
