oj.uz

답안 #81717

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
81717 2018-10-26T10:04:54 Z aminra Teoretičar (COCI18_teoreticar) C++14
52 / 130
 719 ms 104560 KB 
#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.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 504 KB Output is correct
2 Correct 2 ms 932 KB Output is correct
3 Correct 3 ms 1088 KB Output is correct
4 Correct 2 ms 1088 KB Output is correct
5 Correct 2 ms 1088 KB Output is correct

Subtask #2
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 1088 KB Output is correct
2 Correct 3 ms 1092 KB Output is correct
3 Correct 3 ms 1220 KB Output is correct
4 Correct 3 ms 1220 KB Output is correct
5 Correct 3 ms 1220 KB Output is correct

Subtask #3
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 40 ms 36680 KB Output is correct
2 Correct 19 ms 36680 KB Output is correct
3 Correct 51 ms 41812 KB Output is correct
4 Correct 17 ms 41812 KB Output is correct
5 Correct 18 ms 41812 KB Output is correct

Subtask #4
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 18 ms 41812 KB Output is correct
2 Correct 19 ms 41812 KB Output is correct
3 Correct 52 ms 43996 KB Output is correct
4 Correct 13 ms 43996 KB Output is correct
5 Correct 5 ms 43996 KB Output is correct

Subtask #5
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 9 ms 43996 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 10 ms 43996 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #7
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 11 ms 43996 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #8
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 526 ms 43996 KB Output is correct
2 Runtime error 10 ms 43996 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Halted 0 ms 0 KB -

Subtask #9
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 719 ms 104560 KB Output is correct
2 Runtime error 10 ms 104560 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Halted 0 ms 0 KB -

Subtask #10
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 660 ms 104560 KB Output is correct
2 Runtime error 17 ms 104560 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Halted 0 ms 0 KB -