#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int n,m;
struct unpav {
ll a,b,cost;
unpav(ll a, ll b, ll cost) {
this->a=a;
this->b=b;
this->cost=cost;
}
};
vector<unpav> unpavs;
vector<vector<int>> paved(1000);
vector<vector<int>> unpavedCost(1000, vector<int>(1000));
vector<vector<int>> idx(1000, vector<int>(1000));
vector<vector<vector<int>>> path(1000, vector<vector<int>>(1000));
vector<vector<vector<bool>>> pathRequires(1000, vector<vector<bool>>(1000, vector<bool>(1000)));
ll sum = 0;
ll recurs(int node, int blocked) {
//cout << "recurs called with node " << node << " and blocked " << blocked << endl;
ll scenario0 = 0, scenario1=0;
for(int i = 0; i < paved[node].size(); i++) {
if(blocked&(1<<i)) {
continue;
}
scenario0+=recurs(paved[node][i], 1<<idx[paved[node][i]][node]);
}
//cout << "scenario finished " << node << " " << scenario0 << endl;
vector<bool> visited(1000);
visited[node]=true;
deque<int> q;
for(int i = 0; i < paved[node].size(); i++) {
int x = paved[node][i];
//cout << x << endl;
if(blocked&(1<<i)) continue;
q.push_back(x);
visited[x]=true;
}
//cout << " line 38 " << endl;
while(q.size()) {
int x = q.front();
q.pop_front();
for(int y: paved[x]) {
if(visited[y]) continue;
visited[y]=true;
q.push_back(y);
}
}
for(unpav u: unpavs) {
//cout << u.a << " " << u.b << " " << u.cost << endl;
if(!pathRequires[u.a][u.b][node]) continue;
if(path[u.a][u.b].size()%2==0) {
continue;
}
if(unpavedCost[u.a][u.b]==0) continue;
ll here = u.cost;
vector<int> block(1000);
block[node]=blocked;
bool fail = false;
for(int i = 0; i < path[u.a][u.b].size(); i++) {
int p = path[u.a][u.b][i];
if(i==0) {
block[p]|=1<<idx[p][path[u.a][u.b].back()];
block[path[u.a][u.b].back()]|=1<<idx[path[u.a][u.b].back()][p];
} else {
block[p]|=1<<idx[p][path[u.a][u.b][i-1]];
block[path[u.a][u.b][i-1]]|=1<<idx[path[u.a][u.b][i-1]][p];
}
if(!visited[p]) {
fail=true;
break;
}
}
if(fail) continue;
//cout << "NOT failed - Node: " << node << " Blocked: " << blocked << " u: " << u.a << " " << u.b << " " << u.cost << endl;
for(int i = 0; i < n; i++) {
if(block[i]!=0) {
here+=recurs(i, block[i]);
}
}
scenario1=max(scenario1, here);
}
//cout << "scenario 1 finished " << node << " " << scenario1 << endl;
return max(scenario0, scenario1);
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
cin >> n >> m;
for(int i = 0; i < m; i++) {
int a,b,c;
cin >> a >> b >> c;
a--;
b--;
if(c==0) {
paved[a].push_back(b);
paved[b].push_back(a);
idx[a][b]=paved[a].size()-1;
idx[b][a]=paved[b].size()-1;
} else {
unpavs.push_back(unpav(a,b,c));
unpavedCost[a][b]=c;
unpavedCost[b][a]=c;
sum+=c;
}
}
for(int i = 0; i < n; i++) {
vector<bool> visited(n);
visited[i]=true;
deque<vector<int>> q;
vector<int> temp(1, i);
q.push_back(temp);
while(q.size()) {
vector<int> t = q.front();
q.pop_front();
if(unpavedCost[t[0]][t.back()]!=0&&t.size()%2==1) {
for(int j: t) {
path[t[0]][t.back()].push_back(j);
pathRequires[t[0]][t.back()][j]=true;
}
}
for(int j: paved[t.back()]) {
if(visited[j]) continue;
visited[j]=true;
vector<int> s = t;
s.push_back(j);
q.push_back(s);
}
}
}
for(int i = 0; i < n; i++) {
for(int j = 0; j < n; j++) {
cout << i << " " << j << " " << idx[i][j] << endl;
}
}
cout << sum-recurs(0, 0) << endl;
}
Compilation message
training.cpp: In function 'll recurs(int, int)':
training.cpp:23:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
23 | for(int i = 0; i < paved[node].size(); i++) {
| ~~^~~~~~~~~~~~~~~~~~~~
training.cpp:33:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
33 | for(int i = 0; i < paved[node].size(); i++) {
| ~~^~~~~~~~~~~~~~~~~~~~
training.cpp:61:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
61 | for(int i = 0; i < path[u.a][u.b].size(); i++) {
| ~~^~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
156 ms |
211916 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1091 ms |
212088 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1079 ms |
221004 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
155 ms |
211876 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
160 ms |
211932 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1073 ms |
212108 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1089 ms |
212956 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1081 ms |
214860 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1071 ms |
219424 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1089 ms |
214680 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1083 ms |
223632 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
