Submission #330006

#	Time	Username	Problem	Language	Result	Execution time	Memory
330006		EndRay	Programming Contest (POI11_pro)	C++17	100 / 100	172 ms	1516 KiB

pro

#include<bits/stdc++.h>

using namespace std;

const int N = 500+1;

int n, m, r, t, k;

vector<int> g[N];
int mt[N], d[N];

int T;
int used[N];
bool try_dfs(int v, int deg){
    if(used[v] == T)
        return false;
    used[v] = T;
    if(d[v] > deg+1)
        return true;
    for(int u : g[v])
        if(try_dfs(mt[u], deg)){
            --d[mt[u]];
            mt[u] = v;
            ++d[v];
            return true;
        }
    return false;
}

int main(){
    ios_base::sync_with_stdio(false);
    cout.tie(0);
    cin.tie(0);
    cin >> n >> m >> r >> t >> k;
    for(int i = 0; i < k; ++i){
        int u, v;
        cin >> u >> v;
        --u; --v;
        g[u].push_back(v);
    }
    for(int u = 0; u < m; ++u)
        mt[u] = -1;
    for(int v = 0; v < n; ++v)
        for(int u : g[v]) if(mt[u] == -1){
            mt[u] = v;
            ++d[v];
        }
    bool updated = true;
    while(updated){
        updated = false;
        vector<pair<int, int>> ds;
        for(int v = 0; v < n; ++v)
            ds.emplace_back(d[v], v);
        sort(ds.begin(), ds.end());
        ++T;
        for(int i = 0; i < n; ++i){
            int v = ds[i].second;
            if(try_dfs(v, d[v])){
                updated = true;
                break;
            }
        }
    }
    int penalty = 0;
    vector<tuple<int, int, int>> res;
    for(int v = 0; v < n; ++v)
        d[v] = min(d[v], t/r);
    for(int u = 0; u < m; ++u)
        if(mt[u] != -1 && d[mt[u]]){
            penalty += d[mt[u]]*r;
            --d[mt[u]];
            res.emplace_back(mt[u]+1, u+1, d[mt[u]]*r);
        }
    cout << res.size() << " " << penalty << "\n";
    for(auto el : res)
        cout << get<0>(el) << " " << get<1>(el) << " " << get<2>(el) << "\n";
}

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