#include <bits/stdc++.h>
using namespace std;
template <typename T1, typename T2> istream &operator>>(istream &is, const pair<T1, T2> &pa) { is >> pa.first >> pa.second; return is; }
template <typename T> istream &operator>>(istream &is, vector<T> &vec) { for (auto &v : vec) is >> v; return is; }
template <typename T1, typename T2> ostream &operator<<(ostream &os, const pair<T1, T2> &pa) { os << "(" << pa.first << "," << pa.second << ")"; return os; }
template <typename T> ostream &operator<<(ostream &os, const vector<T> &vec) { os << "["; for (auto v : vec) os << v << ","; os << "]"; return os; }
template <typename T> ostream &operator<<(ostream &os, const deque<T> &vec) { os << "deq["; for (auto v : vec) os << v << ","; os << "]"; return os; }
template <typename T> ostream &operator<<(ostream &os, const set<T> &vec) { os << "{"; for (auto v : vec) os << v << ","; os << "}"; return os; }
template <typename T> ostream &operator<<(ostream &os, const multiset<T> &vec) { os << "{"; for (auto v : vec) os << v << ","; os << "}"; return os; }
template <typename T> ostream &operator<<(ostream &os, const unordered_set<T> &vec) { os << "{"; for (auto v : vec) os << v << ","; os << "}"; return os; }
template <typename T> ostream &operator<<(ostream &os, const unordered_multiset<T> &vec) { os << "{"; for (auto v : vec) os << v << ","; os << "}"; return os; }
template <typename TK, typename TV> ostream &operator<<(ostream &os, const unordered_map<TK, TV> &mp) { os << "{"; for (auto v : mp) os << v.first << "=>" << v.second << ","; os << "}"; return os; }
template <typename TK, typename TV> ostream &operator<<(ostream &os, const map<TK, TV> &mp) { os << "{"; for (auto v : mp) os << v.first << "=>" << v.second << ","; os << "}"; return os; }
template <typename T> void resize_array(vector<T> &vec, int len) { vec.resize(len); }
template <typename T, typename... Args> void resize_array(vector<T> &vec, int len, Args... args) { vec.resize(len); for (auto &v : vec) resize_array(v, args...); }
template <typename T1, typename T2> pair<T1, T2> operator+(const pair<T1, T2> &l, const pair<T1, T2> &r) { return make_pair(l.first + r.first, l.second + r.second); }
template <typename T1, typename T2> pair<T1, T2> operator-(const pair<T1, T2> &l, const pair<T1, T2> &r) { return make_pair(l.first - r.first, l.second - r.second); }
long long gcd(long long a, long long b) { return b ? gcd(b, a % b) : a; }
mt19937 mrand(random_device{}());
int rnd(int x) { return mrand() % x; }
template <unsigned int MOD>
class ModInt {
public:
ModInt(unsigned long long _v = 0) { set_v((_v % MOD + MOD)); }
explicit operator bool() const { return val != 0; }
ModInt operator-() const { return ModInt() - *this; }
ModInt operator+(const ModInt &r) const { return ModInt().set_v(val + r.val); }
ModInt operator-(const ModInt &r) const { return ModInt().set_v(val + MOD - r.val); }
ModInt operator*(const ModInt &r) const { return ModInt().set_v((unsigned int)((unsigned long long)(val)*r.val % MOD)); }
ModInt operator/(const ModInt &r) const { return *this * r.inv(); }
ModInt &operator+=(const ModInt &r) { return *this = *this + r; }
ModInt &operator-=(const ModInt &r) { return *this = *this - r; }
ModInt &operator*=(const ModInt &r) { return *this = *this * r; }
ModInt &operator/=(const ModInt &r) { return *this = *this / r; }
// ModInt &operator=(unsigned long long _v) { set_v((_v % MOD + MOD)); return *this; }
unsigned int operator=(unsigned long long _v) { set_v((_v % MOD + MOD)); return val; }
bool operator==(const ModInt &r) const { return val == r.val; }
bool operator!=(const ModInt &r) const { return val != r.val; }
ModInt pow(long long n) const {
ModInt x = *this, r = 1;
while (n) {
if (n & 1)
r *= x;
x *= x;
n >>= 1;
}
return r;
}
ModInt inv() const { return pow(MOD - 2); }
unsigned int get_val() { return val; }
friend ostream &operator<<(ostream &os, const ModInt &r) { return os << r.val; }
friend istream &operator>>(istream &is, ModInt &r) { return is >> r.val; }
private:
unsigned int val;
ModInt &set_v(unsigned int _v) {
val = (_v < MOD) ? _v : _v - MOD;
return *this;
}
};
constexpr unsigned int mod = 1e9+7;
using Mint = ModInt<mod>;
int n,m;
const int LOG=11;
#define LSOne(S) (S & (-S))
vector<vector<int>> paved;
vector<vector<int>> child;
vector<vector<int>> indN;
vector<vector<pair<int,int>>> memo2;
vector<int> depth;
vector<vector<int>> parent;
vector<vector<pair<pair<int,int>,int>>> edges;
vector<vector<int>> memo;
vector<int> maskCalc;
int lca(int a, int b){
if(depth[b]>depth[a]) swap(a,b);
int k=depth[a]-depth[b];
for (int j = LOG-1; j >= 0; j--) if(k&(1<<j)) a=parent[a][j];
if(a==b) return a;
for (int j = LOG-1; j >= 0; j--)
{
if(parent[a][j]!=parent[b][j]) {
a=parent[a][j];
b=parent[b][j];
}
}
return parent[a][0];
}
int dp(int x, int mask, int prev){
if(memo[x][mask]!=-1) return memo[x][mask];
if(child[x].size()==0) return memo[x][mask]=0;
int mx=0;
if(__builtin_popcount(mask)>=child[x].size()) return memo[x][mask]=0;
if(prev==-1){
if(maskCalc[x]==-1){
for (int i = 0; i < child[x].size(); i++)
{
if((mask&(1<<i))!=0) continue;
mx+=dp(child[x][i],0,-1);
}
maskCalc[x]=mx;
}else{
int dfMask=mask;
mx=maskCalc[x];
while(dfMask>0) {
int ls=LSOne(dfMask);
mx-=dp(child[x][ls-1],0,-1);
dfMask-=(1<<(ls-1));
}
}
}
prev=mx;
for(auto u : edges[x]) {
int a=u.first.first;
int b=u.first.second;
int c=u.second;
int d=(depth[a]+depth[b])-2*depth[x];
if(d%2!=0) continue;
if(memo2[a][b].first==-1){
int ap=a;
int bp=b;
int sum=0;
while((parent[ap][0]!=x&&ap!=x)||(parent[bp][0]!=x&&bp!=x)){
if((parent[ap][0]!=x&&ap!=x)){
int bitmaskA=(1<<indN[parent[ap][0]][ap]);
sum+=dp(parent[ap][0],bitmaskA,-1);
ap=parent[ap][0];
}
if((parent[bp][0]!=x&&bp!=x)){
int bitmaskB=(1<<indN[parent[bp][0]][bp]);
sum+=dp(parent[bp][0],bitmaskB,-1);
bp=parent[bp][0];
}
}
int bitmask=0;
if(a!=x) {
sum+=dp(a,0,-1);
bitmask+=(1<<indN[x][ap]);
}
if(b!=x) {
sum+=dp(b,0,-1);
bitmask+=(1<<indN[x][bp]);
}
memo2[a][b]={sum,bitmask};
}
if((memo2[a][b].second&mask)!=0) continue;
int new_prev=prev;
if(a!=x) new_prev-=dp(a,0,-1);
if(b!=x) new_prev-=dp(b,0,-1);
mx=max(mx,memo2[a][b].first+c+dp(x,memo2[a][b].second,new_prev));
}
return memo[x][mask]=mx;
}
signed main() {
// Input:
ios::sync_with_stdio(false); cin.tie(nullptr);
cin>>n>>m;
paved.resize(n+1);
depth.resize(n+1);
maskCalc.resize(n+1,-1);
parent.resize(n+1, vector<int>(LOG, 0));
indN.resize(n+1, vector<int>(n+1, -1));
memo2.resize(n+1, vector<pair<int,int>>(n+1,{-1,-1}));
memo.resize(n+1, vector<int>(pow(2,10)+2,-1));
edges.resize(n+1);
child.resize(n+1);
int sum=0;
vector<pair<pair<int,int>, int>> edgesTOPROCESS;
for (int i = 0; i < m; i++)
{
int a,b,c; cin >> a >> b >> c;
sum+=c;
if(a>b) swap(a,b);
if(c==0) {
paved[a].push_back(b);
paved[b].push_back(a);
}
else {
edgesTOPROCESS.push_back({{a,b},c});
}
}
queue<int> q;
q.push(1);
parent[1][0]=1;
depth[1]=0;
vector<bool> visited(n+1);
while(!q.empty()){
int x=q.front(); q.pop();
visited[x]=true;
for (auto u: paved[x])
{
if(visited[u]) continue;
q.push(u);
indN[x][u]=child[x].size();
child[x].push_back(u);
parent[u][0]=x;
depth[u]=depth[x]+1;
}
}
for (int j = 1; j < LOG; j++) for (int i = 1; i <= n; i++) parent[i][j]=parent[parent[i][j-1]][j-1];
for (int i = 0; i < m-(n-1); i++)
{
int a=edgesTOPROCESS[i].first.first;
int b=edgesTOPROCESS[i].first.second;
int c=edgesTOPROCESS[i].second;
int lc=lca(a,b);
int d=(depth[a]+depth[b])-2*depth[lc];
if(d%2!=0) continue;
edges[lc].push_back({{a,b},c});
}
cout << sum-dp(1,0,-1) << "\n";
return 0;
}
Compilation message
training.cpp: In function 'int dp(int, int, int)':
training.cpp:100:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
100 | for (int i = 0; i < child[x].size(); i++)
| ~~^~~~~~~~~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
344 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Execution timed out |
477 ms |
524288 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
13 ms |
16476 KB |
Output is correct |
| 2 |
Correct |
14 ms |
16768 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Execution timed out |
332 ms |
524288 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Execution timed out |
335 ms |
524288 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Execution timed out |
342 ms |
524288 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Execution timed out |
370 ms |
524288 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Execution timed out |
326 ms |
524288 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Execution timed out |
382 ms |
524288 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Execution timed out |
336 ms |
524288 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Execution timed out |
339 ms |
524288 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
