Submission #795911

#TimeUsernameProblemLanguageResultExecution timeMemory
795911vgoofficialTraining (IOI07_training)C++14
0 / 100
1091 ms223632 KiB
#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 (stderr)

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 timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...