oj.uz

Submission #81711

# Submission time Handle Problem Language Result Execution time Memory
81711 2018-10-26T09:49:01 Z Saboon Teoretičar (COCI18_teoreticar) C++14
0 / 130
 12000 ms 25268 KB 
#include <iostream>
#include <sstream>
#include <queue>
#include <stack>
#include <vector>
#include <cstring>
#include <cmath>
#include <map>
#include <unordered_map>
#include <set>
#include <algorithm>
#include <iomanip>
#define F first
#define S second
#define PB push_back
#define PF push_front
#define MP make_pair
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
const int maxn = 1e5 + 37;
const int maxm = 6e5 + 100;
const int inf = 1e9;

int col[maxn];
bool visited[maxn];

int to[2 * maxm], cap[2 * maxm], pre[2 * maxn], last[2 * maxn], pos[2 * maxn];

int n, m, e, c;

int dis[2 * maxn];
bool bfs (int src, int sink) {
    queue <int> q;
    q.push (src);
    memset (dis, -1, sizeof dis);
    dis[src] = 0;
    while (!q.empty()) {
        int v = q.front();
        q.pop();
        for (int ed = last[v]; ed != -1; ed = pre[ed]) {
            if (cap[ed] and dis[to[ed]] == -1) {
                dis[to[ed]] = dis[v] + 1;
                q.push (to[ed]);
            }
        }
    }
    return dis[sink] != -1;
}

int dfs (int src, int sink, int untilnow) {
    if (src == sink)
        return untilnow;
    int now = 0;
    for (int &ed = pos[src]; ed != -1; ed = pre[ed]) {
        if (cap[ed] and dis[to[ed]] == dis[src] + 1) {
            int cur = dfs (to[ed], sink, min (cap[ed], untilnow));
            cap[ed] -= cur, cap[ed ^ 1] += cur, now += cur, untilnow -= cur;
            if (untilnow == 0)
                return now;
        }
    }
    return now;
}

int max_flow () {
    int src = n + m + 1, sink = n + m + 2;
    ll ret = 0;
    while (bfs (src, sink)) {
        for (int i = 1; i <= sink; i++)
            pos[i] = last[i];
        ret += dfs (src, sink, inf);
    }
    for (int i = 0; i < 2 * e; i += 2) {
        if (cap[i] == 0 and col[i] == 0) {
            col[i] = c;
            cap[i ^ 1] = 0;
        }
    }
    return ret;
}

int tmp = 0;
void add_edge (int fi, int se, int ca) {
    to[tmp] = se, cap[tmp] = ca, pre[tmp] = last[fi], last[fi] = tmp ++;
    to[tmp] = fi, cap[tmp] = 0, pre[tmp] = last[se], last[se] = tmp ++;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin >> n >> m >> e;
    memset (last, -1, sizeof last);
    for (int i = 0; i < e; i++) {
        int v, u;
        cin >> v >> u;
        add_edge (v, u + n, 1);
    }
    int src = n + m + 1, sink = n + m + 2;
    for (int i = 1; i <= n; i++)
        add_edge (src, i, 0);
    for (int i = 1; i <= m; i++)
        add_edge (n + i, sink, 0);
    c = 1;
    int cop = e;
    while (cop) {
        for (int ed = last[src]; ed != -1; ed = pre[ed])
            cap[ed] ++;
        for (int i = 1; i <= m; i++)
            cap[last[i + n]] ++;

        cop -= max_flow();
        c ++;
    }
    cout << c - 1 << endl;
    for (int i = 0; i < 2 * e; i += 2)
        cout << col[i] << '\n';
}

Subtask #1
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 1912 KB not colored properly
2 Halted 0 ms 0 KB -

Subtask #2
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 2044 KB not colored properly
2 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 12 ms 2376 KB not colored properly
2 Halted 0 ms 0 KB -

Subtask #4
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 48 ms 2404 KB not colored properly
2 Halted 0 ms 0 KB -

Subtask #5
0 / 13.0

# Verdict Execution time Memory Grader output
1 Execution timed out 12037 ms 12764 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Execution timed out 12049 ms 12780 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #7
0 / 13.0

# Verdict Execution time Memory Grader output
1 Runtime error 158 ms 25268 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #8
0 / 13.0

# Verdict Execution time Memory Grader output
1 Runtime error 293 ms 25268 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #9
0 / 13.0

# Verdict Execution time Memory Grader output
1 Runtime error 160 ms 25268 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #10
0 / 13.0

# Verdict Execution time Memory Grader output
1 Runtime error 121 ms 25268 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -