UOJ509

Solution

Subtask1: A = 3, B = 0

对于A3A \ge 3,预处理从00开始到每个点的最短路did_i

(x,y)(x, y)的颜色设为

那么一个点连出去的颜色最多只有两种,设为a,ba, b

我们走颜色cc,满足c=ac = a 即可

Subtask1: A = 2, B = 6, m = n - 1

考虑对深度为dd的边染 的颜色,那么只要走到某个点的度数2\ne 2即可判断方向

所以只需要处理一段链的情况

考虑对链上的边进行以110100110100为循环的染色,构造如下操作树:

1
2
3
4
5
6
7
8
9
10
11
12
13
00->询问0,1
11:反向
01:正向
11->询问1,0
01:反向
00:正向
10->询问1
11->询问1,0
00:正向
10:反向
10->询问0
00:反向
10:正向

不难发现如此构造可以在3步内找到方向,不超过3步回到原点,总步数不超过d+6d + 6

Code

Anthony

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
#include "Anthony.h"
#include <iostream>
#include <ctime>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <climits>
#include <queue>
#include <set>
#include <cmath>
#include <map>
#include <bitset>
#include <fstream>
#include <tr1/unordered_map>
#include <assert.h>

#define x first
#define y second
#define y0 Y0
#define y1 Y1
#define mp make_pair
#define pb push_back
#define DEBUG(x) cout << #x << " = " << x << endl;

using namespace std;

typedef long long LL;
typedef pair <int, int> pii;

template <typename T> inline int Chkmax (T &a, T b) { return a < b ? a = b, 1 : 0; }
template <typename T> inline int Chkmin (T &a, T b) { return a > b ? a = b, 1 : 0; }
template <typename T> inline T read ()
{
T sum = 0, fl = 1; char ch = getchar();
for (; !isdigit(ch); ch = getchar()) if (ch == '-') fl = -1;
for (; isdigit(ch); ch = getchar()) sum = (sum << 3) + (sum << 1) + (ch - '0');
return sum * fl;
}

inline void proc_status ()
{
ifstream t ("/proc/self/status");
cerr << string (istreambuf_iterator <char> (t), istreambuf_iterator <char> ()) << endl;
}

const int MAXN = 2e4;

namespace S1
{
vector <pii> G[MAXN + 5];

int dep[MAXN + 5];

inline void add_edge (int x, int y, int i) { G[x].pb (mp (y, i)); G[y].pb (mp (x, i)); }

vector <int> work (int N, int M, int A, int B, vector<int> U, vector<int> V)
{
for (int i = 0; i < M; ++i) add_edge (U[i], V[i], i);

for (int i = 0; i < N; ++i) dep[i] = 0x3f3f3f3f;
dep[0] = 0;

static queue <int> Q; Q.push (0);

while (!Q.empty())
{
int u = Q.front(); Q.pop();

for(auto x : G[u])
{
int y = x.x;
if (dep[y] > dep[u] + 1)
dep[y] = dep[u] + 1, Q.push (y);
}
}

static vector <int> col; col.resize(M);

for (int i = 0; i < N; ++i)
for (auto x : G[i])
{
if (dep[x.x] == dep[i])
col[x.y] = (dep[i] + 1) % 3;
else if (dep[x.x] == dep[i] - 1)
col[x.y] = dep[i] % 3;
}

return col;
}
}

namespace S2
{
vector <pii> G[MAXN + 5];
vector <int> ans;
int bkt[] = {1, 1, 0, 1, 0, 0};

inline void dfs (int x, int f, int d)
{
int son = G[x].size() - (x != 0);

for (auto t : G[x])
{
int y = t.x, id = t.y;
if (id == f) continue;
if (son != 1)
{
ans[id] = !ans[f];
dfs (y, id, ans[id] ? 0 : 2);
}
else
{
ans[id] = bkt[(d + 1) % 6];
dfs (y, id, (d + 1) % 6);
}

}
}

vector <int> work (int N, int M, int A, int B, vector <int> U, vector <int> V)
{
for (int i = 0; i < M; ++i) G[U[i]].pb (mp (V[i], i)), G[V[i]].pb (mp (U[i], i));

ans.resize (M);
dfs (0, -1, 0);

return ans;
}
}

vector <int> Mark (int N, int M, int A, int B, vector <int> U, vector <int> V)
{
if (A >= 3) return S1 :: work (N, M, A, B, U, V);
return S2 :: work (N, M, A, B, U, V);
}

Catherine

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
#include "Catherine.h"
#include <iostream>
#include <ctime>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <climits>
#include <queue>
#include <set>
#include <cmath>
#include <map>
#include <bitset>
#include <fstream>
#include <tr1/unordered_map>
#include <assert.h>

#define x first
#define y second
#define y0 Y0
#define y1 Y1
#define mp make_pair
#define pb push_back
#define DEBUG(x) cout << #x << " = " << x << endl;

using namespace std;

typedef long long LL;
typedef pair <int, int> pii;

template <typename T> inline int Chkmax (T &a, T b) { return a < b ? a = b, 1 : 0; }
template <typename T> inline int Chkmin (T &a, T b) { return a > b ? a = b, 1 : 0; }
template <typename T> inline T read ()
{
T sum = 0, fl = 1; char ch = getchar();
for (; !isdigit(ch); ch = getchar()) if (ch == '-') fl = -1;
for (; isdigit(ch); ch = getchar()) sum = (sum << 3) + (sum << 1) + (ch - '0');
return sum * fl;
}

inline void proc_status ()
{
ifstream t ("/proc/self/status");
cerr << string (istreambuf_iterator <char> (t), istreambuf_iterator <char> ()) << endl;
}

int A, B;

void Init (int _A, int _B) { A = _A, B = _B; }

namespace S1
{
int lst = -1;

inline int work (vector <int> y)
{
if (lst != -1) y[lst]++;
if (y[0] && y[1]) return lst = 0;
if (y[0] && y[2]) return lst = 2;
if (y[1] && y[2]) return lst = 1;
if (y[0]) return lst = 0;
if (y[1]) return lst = 1;
if (y[2]) return lst = 2;
}
}

namespace S2
{
int chk_dir, lst = -1;
vector <int> x;

#define deg (y[0] + y[1])

inline int only (vector <int> y) { if (lst != -1) --y[lst]; return y[0] ? 0 : 1; }

inline int work (vector <int> y)
{
if (chk_dir)
{
if (deg == 1) return lst = (y[0] ? 0 : 1);
return lst ^= 1;
}
else
{
if (lst != -1) ++y[lst];

if (deg != 2)
{
chk_dir = 1;

int d = (y[0] == 1 ? 0 : 1);
if (lst == -1) return lst = d;
if (lst == d) return -1;
return lst = d;
}

x.pb (y[1]);

if (x.size() == 1)
{
if (x[0] == 0 || x[0] == 2) return lst = only (y);
return lst = 1;
}

if (x.size() == 2) return lst = only (y);

if (x.size() == 3)
{
if (x[0] == 0)
{
chk_dir = 1;
if (x[2] == 2) { lst = 1; return -1; }
return lst = 0;
}

if (x[0] == 2)
{
chk_dir = 1;
if (x[2] == 1) { lst = 0; return -1; }
return lst = 0;
}

if (x[1] == 2) return lst = 0;

chk_dir = 1;

if (x[2] == 0) { lst = 0; return -1; }
return lst = 1;
}

if (x.size() == 4)
{
chk_dir = 1;
if (x[3] == 1) { lst = 0; return -1; }
return lst = 0;
}

puts("fuck");
exit (0);
}
}

/*
00->询问0,1
11:反向
01:正向
11->询问1,0
01:反向
00:正向
10->询问1
11->询问1,0
00:正向
10:反向
10->询问0
00:反向
10:正向
*/
}

int Move (vector <int> y)
{
if (A >= 3) return S1 :: work (y);
return S2 :: work (y);
}