Submission #795902

#	Time	Username	Problem	Language	Result	Execution time	Memory
795902		vgoofficial	Training (IOI07_training)	C++14	0 / 100	1095 ms	524288 KiB

training

#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;
    ll totalCost = 0;
    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();
            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++) {
      |                        ~~^~~~~~~~~~~~~~~~~~~~~~~
training.cpp: In function 'int main()':
training.cpp:91:8: warning: unused variable 'totalCost' [-Wunused-variable]
   91 |     ll totalCost = 0;
      |        ^~~~~~~~~

• Subtask 1: 0 / 10
• Subtask 2: 0 / 10
• Subtask 3: 0 / 10
• Subtask 4: 0 / 7
• Subtask 5: 0 / 9
• Subtask 6: 0 / 9
• Subtask 7: 0 / 9
• Subtask 8: 0 / 9
• Subtask 9: 0 / 9
• Subtask 10: 0 / 9
• Subtask 11: 0 / 9