oj.uz

Submission #330006

# Submission time Handle Problem Language Result Execution time Memory
330006 2020-11-23T11:53:12 Z EndRay Programming Contest (POI11_pro) C++17
100 / 100
 172 ms 1516 KB 
#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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 0 ms 364 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 492 KB Output is correct
2 Correct 7 ms 492 KB Output is correct
3 Correct 1 ms 364 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 82 ms 1004 KB Output is correct
2 Correct 71 ms 876 KB Output is correct
3 Correct 1 ms 364 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 952 KB Output is correct
2 Correct 41 ms 620 KB Output is correct
3 Correct 1 ms 364 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 96 ms 1004 KB Output is correct
2 Correct 37 ms 620 KB Output is correct
3 Correct 1 ms 492 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 492 KB Output is correct
2 Correct 57 ms 876 KB Output is correct
3 Correct 86 ms 1024 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 876 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 620 KB Output is correct
2 Correct 172 ms 1516 KB Output is correct
3 Correct 5 ms 364 KB Output is correct