Submission #208930

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
208930	2020-03-12T15:11:33 Z	Mercenary	Programming Contest (POI11_pro)	C++14	100 / 100	594 ms	10360 KB

#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/trie_policy.hpp>
using namespace std;
using namespace __gnu_pbds;

#define taskname "A"
#define pb	push_back
#define mp 	make_pair


typedef long double ld;
typedef long long ll;
typedef pair<int,int> ii;
typedef tree <ii,null_type,less<ii>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;

const int maxn = 500 + 5;
const int inf = 1e6;

struct edge{
    int u , v , c;
    edge(){};edge(int u , int v , int c):u(u),v(v),c(c){};
}e[maxn * maxn * 2];

vector<int> adj[maxn * 2];

int nTime = 0 , s , t;

void add_edge(int u , int v , int c){
    e[nTime * 2] = edge(u,v,c);
    e[nTime * 2 + 1] = edge(v,u,0);
    adj[u].pb(nTime * 2);adj[v].pb(nTime*2+1);
    ++nTime;
}

int d[maxn * 2];
int trace[maxn * 2];
bool vis[maxn * 2];

bool spfa(){
    queue<int> q;
    fill_n(d,maxn*2,inf);fill_n(trace,maxn*2,-1);
    q.push(s);
    d[s] = 0;
    while(q.size()){
        auto u = q.front();q.pop();vis[u] = 0;
        for(int c : adj[u]){
            if(e[c].c > 0 && d[e[c].v] > 0){
                d[e[c].v] = 0;
                trace[e[c].v] = c;
                if(vis[e[c].v] == 0){
                    vis[e[c].v] = 1;
                    q.push(e[c].v);
                }
            }
        }
    }
    return d[t] != inf;
}

int n , m , R , T , K;
ii a[maxn * maxn];
int deg[maxn];

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    if(fopen(taskname".INP","r")){
        freopen(taskname".INP", "r",stdin);
        freopen(taskname".OUT", "w",stdout);
    }
    cin >> n >> m >> R >> T >> K;
    s = 0 , t = n + m + 1;
    for(int i = 1 ; i <= K ; ++i){
        int u, v;cin >> u >> v;
        a[i] = mp(u,v);
        add_edge(u,v+n,1);
    }
    for(int i = 1 ; i <= m ; ++i){
        add_edge(i + n , t , 1);
    }
    for(int i = 1 ; i <= n ; ++i){
        add_edge(s , i , 1);
    }
    int res1 = 0, res = 0;
    for(int j = 1 ; j * R <= T && res1 < m ; ++j){
        for(int i = 0 ; i < n ; ++i){
            e[(i + K + m) * 2].c = 1;
            e[(i + K + m) * 2 + 1].c = 0;
        }
        while(spfa()){
            int delta = 1;
            for(int u = t ; u != s ; u = e[trace[u]].u){
                e[trace[u]].c -= delta;e[trace[u]^1].c += delta;
            }
            res += j;
            res1++;
        }
    }
    cout << res1 << " " << (ll)res * R << '\n';
    for(int i = 1 ; i <= K ; ++i){
        if(e[(i - 1) * 2].c == 0){
            cout << a[i].first << " " << a[i].second << " " << R * deg[a[i].first]++ << '\n';
        }
    }
}

Compilation message

pro.cpp: In function 'int main()':
pro.cpp:70:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
         freopen(taskname".INP", "r",stdin);
         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
pro.cpp:71:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
         freopen(taskname".OUT", "w",stdout);
         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	6 ms	504 KB	Output is correct
2	Correct	5 ms	376 KB	Output is correct

Subtask #4
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	25 ms	1144 KB	Output is correct
2	Correct	37 ms	1144 KB	Output is correct
3	Correct	7 ms	376 KB	Output is correct

Subtask #5
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	241 ms	4472 KB	Output is correct
2	Correct	234 ms	4600 KB	Output is correct
3	Correct	6 ms	504 KB	Output is correct

Subtask #6
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	201 ms	3832 KB	Output is correct
2	Correct	158 ms	1764 KB	Output is correct
3	Correct	10 ms	504 KB	Output is correct

Subtask #7
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	269 ms	5392 KB	Output is correct
2	Correct	138 ms	2552 KB	Output is correct
3	Correct	9 ms	376 KB	Output is correct

Subtask #8
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	54 ms	1152 KB	Output is correct
2	Correct	19 ms	3832 KB	Output is correct
3	Correct	277 ms	4988 KB	Output is correct

Subtask #9
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	218 ms	4088 KB	Output is correct
2	Correct	5 ms	504 KB	Output is correct
3	Correct	10 ms	376 KB	Output is correct

Subtask #10
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	77 ms	1528 KB	Output is correct
2	Correct	594 ms	10360 KB	Output is correct
3	Correct	19 ms	508 KB	Output is correct