제출 #81717

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
81717		aminra	Teoretičar (COCI18_teoreticar)	C++14	52 / 130	719 ms	104560 KiB

teoreticar

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MOD = 1e9 + 7;
const int MAXN = (int)5007;
const int MAXS = (int)5e5 + 7;
const int infint = (int)1e9;
const ll inf = (ll)1e18;
int color[2][MAXN][MAXN];
int id[MAXN][MAXN];
int ans[MAXS], a, b, m;
void dfs(int p, int u, int v, int c1, int c2)
{
    int tmp = color[1 - p][v][c1];
    color[p][u][c1] = v;
    color[1 - p][v][c1] = u;
    if(!tmp)
    {
        color[1 - p][v][c2] = 0;
        return;
	}
    dfs(1 - p, v, tmp, c2, c1);
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    cin >> a >> b >> m;
    int cnt = 0;
    for(int i = 1; i <= m; i++)
    {
        int u, v;
        cin >> u >> v;
        id[u][v] = i;
        int c1 = 1, c2 = 1;
        while(color[0][u][c1]) c1++;
        while(color[1][v][c2]) c2++;
        cnt = max(cnt, max(c1,c2));
        if(c1 == c2)
        	color[0][u][c1]=v, color[1][v][c1]=u;
		else
            dfs(0, u, v, c1, c2);
    }
	cout << cnt << "\n";
    for(int i = 1; i <= a; i++)
        for(int j = 1; j <= cnt; j++)
        	if(color[0][i][j] != 0)
            	ans[id[i][color[0][i][j]]] = j;
    for (int i = 1; i <= m; i++)
        cout << ans[i] << " ";
}

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