QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#188267#1092. Burnished Security UpdatesAs3b_team_f_masr#WA 19ms55656kbC++141.0kb2023-09-25 17:58:582023-09-25 17:58:58

Judging History

你现在查看的是最新测评结果

  • [2023-09-25 17:58:58]
  • 评测
  • 测评结果:WA
  • 用时:19ms
  • 内存:55656kb
  • [2023-09-25 17:58:58]
  • 提交

answer

#include <bits/stdc++.h>

typedef long double ld;
typedef long long ll;
using namespace std;
int di[] = {1, 0, -1, 0, 0, 1, -1, 1};
int dj[] = {0, 1, 0, -1, -1, 0, 1, -1};

const ll oo = 1e18;
const int N = 2e6 + 5, M = 1e4 + 5, MOD = 1e9 + 7;
#define EPS 1e-9

int n, m, a[N], vis[N], col[N], w, b, no;
vector<int> v[N];

void dfs(int node, int color) {
    vis[node] = 1;
    col[node] = color;
    if (color) b++;
    else w++;
    for (auto x:v[node]) {
        if (vis[x]) {
            if (col[node] == col[x]) no = 1;
        } else dfs(x, !color);
    }
}

int main() {
    ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    //memset(dp, -1, sizeof dp);
    cin >> n >> m;
    while (m--) {
        int x, y;
        cin >> x >> y;
        v[x].push_back(y);
        v[y].push_back(x);
    }
    int ans = 0;
    for (int i = 1; i <= n; i++) {
        if (!vis[i]) {
            w = b = 0;
            dfs(i, 0);
            ans += max(w, b);
        }
    }
    cout << (no ? -1 : ans);
    return 0;
}

详细

Test #1:

score: 100
Accepted
time: 3ms
memory: 50472kb

input:

4 2
1 2
3 4

output:

2

result:

ok 1 number(s): "2"

Test #2:

score: 0
Accepted
time: 0ms
memory: 50436kb

input:

4 4
1 2
2 3
3 4
1 4

output:

2

result:

ok 1 number(s): "2"

Test #3:

score: 0
Accepted
time: 9ms
memory: 50732kb

input:

4 3
1 2
2 3
1 3

output:

-1

result:

ok 1 number(s): "-1"

Test #4:

score: 0
Accepted
time: 13ms
memory: 55656kb

input:

300000 49525
14 7
8 10
25 22
33 32
33 36
33 38
35 34
36 34
34 40
35 41
39 36
40 38
53 52
53 57
54 55
56 54
59 61
59 64
64 61
71 73
71 74
77 71
71 79
77 72
74 73
77 78
80 84
80 85
96 100
100 103
126 125
149 150
153 154
154 159
157 155
156 160
158 160
164 162
169 167
169 168
168 173
173 169
171 170
17...

output:

-1

result:

ok 1 number(s): "-1"

Test #5:

score: 0
Accepted
time: 14ms
memory: 55208kb

input:

299996 49689
7 10
20 19
27 26
49 44
47 48
63 57
63 58
61 59
59 62
62 60
60 64
65 74
71 66
77 76
88 84
98 99
115 118
121 115
121 116
130 126
135 141
141 139
142 143
178 174
182 180
185 189
187 193
191 190
222 227
231 235
238 239
243 240
247 240
247 246
257 254
258 256
264 266
271 267
274 268
282 279
...

output:

-1

result:

ok 1 number(s): "-1"

Test #6:

score: 0
Accepted
time: 19ms
memory: 55304kb

input:

299993 49815
10 12
15 18
19 21
28 31
47 52
53 52
59 55
65 62
62 66
73 72
72 76
90 85
92 85
93 85
90 92
97 94
96 100
100 99
101 103
105 104
104 107
111 105
107 112
117 115
121 117
117 124
119 121
122 120
122 123
137 133
152 151
163 161
168 169
173 172
200 201
212 215
217 215
231 224
228 229
243 241
2...

output:

-1

result:

ok 1 number(s): "-1"

Test #7:

score: 0
Accepted
time: 13ms
memory: 55364kb

input:

299991 49386
15 12
26 19
22 23
24 22
24 23
25 27
32 36
36 34
35 38
55 54
57 54
59 62
61 60
61 64
63 62
72 71
76 74
83 78
85 81
85 82
86 87
92 86
93 95
107 110
112 108
114 115
115 119
121 115
120 116
121 120
133 131
156 160
160 164
162 161
162 163
180 178
184 186
187 184
188 186
188 189
221 220
227 2...

output:

-1

result:

ok 1 number(s): "-1"

Test #8:

score: 0
Accepted
time: 19ms
memory: 55188kb

input:

299993 48776
5 2
3 4
9 7
11 12
14 12
26 28
35 38
47 49
60 57
57 64
62 58
65 60
65 62
76 68
81 79
80 83
80 84
83 82
83 85
89 90
99 98
104 102
111 107
111 108
112 114
120 122
140 135
150 143
144 149
157 158
159 162
164 167
169 165
172 166
171 170
190 188
195 194
195 198
209 210
230 229
239 240
261 257...

output:

-1

result:

ok 1 number(s): "-1"

Test #9:

score: 0
Accepted
time: 13ms
memory: 55208kb

input:

299997 50016
4 2
6 2
8 9
22 21
24 21
23 22
34 38
35 37
45 44
53 56
61 53
54 57
58 54
54 61
60 56
57 58
60 58
61 58
70 75
79 81
79 84
85 79
79 87
80 81
82 81
85 83
95 93
102 98
99 102
112 111
137 136
138 141
151 152
159 157
177 171
172 174
181 178
188 183
186 190
189 188
194 195
198 202
205 198
199 2...

output:

-1

result:

ok 1 number(s): "-1"

Test #10:

score: 0
Accepted
time: 14ms
memory: 55192kb

input:

299991 49337
22 30
31 29
37 35
47 42
62 71
63 66
66 68
74 75
79 86
80 83
91 90
104 102
102 108
118 120
139 135
139 140
150 146
154 152
155 154
164 159
166 169
166 170
171 177
174 180
189 192
217 213
232 234
240 242
247 244
246 248
247 249
254 251
270 272
272 273
283 282
286 284
289 284
284 290
287 2...

output:

-1

result:

ok 1 number(s): "-1"

Test #11:

score: -100
Wrong Answer
time: 12ms
memory: 53736kb

input:

299991 18824
7 3
13 8
12 10
36 30
34 37
46 44
48 44
73 67
106 102
104 108
139 134
135 139
145 141
144 142
175 177
189 194
190 193
210 206
214 213
253 249
253 250
283 286
302 294
309 304
311 305
345 349
381 382
393 391
391 398
408 406
417 412
427 421
463 459
517 520
531 527
542 541
559 560
574 576
60...

output:

284286

result:

wrong answer 1st numbers differ - expected: '15705', found: '284286'