oj.uz

답안 #329997

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
329997 2020-11-23T11:24:48 Z EndRay Programming Contest (POI11_pro) C++17
0 / 100
 20 ms 876 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];

bool used[N];
bool try_dfs(int v, int deg){
    if(used[v])
        return false;
    used[v] = true;
    if(d[v] > deg+1)
        return true;
    for(int u : g[v])
        if(mt[u] != -1 && 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;
        for(int i = 0; i < n; ++i)
            used[i] = false;
        for(int v = 0; v < n; ++v){
            if(try_dfs(v, d[v]))
                updated = true;
        }
    }
    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
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 364 KB It was possible to solve 100 problems and you solved only 52.
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 364 KB It was possible to solve 95 problems and you solved only 61.

Subtask #3
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 364 KB It was possible to solve 80 problems and you solved only 10.
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 3 ms 492 KB It was possible to solve 200 problems and you solved only 67.
2 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 16 ms 876 KB It was possible to solve 494 problems and you solved only 8.
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 12 ms 876 KB It was possible to solve 500 problems and you solved only 30.
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 20 ms 876 KB It was possible to solve 500 problems and you solved only 6.
2 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 4 ms 492 KB It was possible to solve 390 problems and you solved only 97.
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 13 ms 876 KB It was possible to get penalty of 500 points and you received 24292.
2 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 6 ms 492 KB It was possible to solve 452 problems and you solved only 127.
2 Halted 0 ms 0 KB -