XJTUOJ 首页 题库 比赛 评测 排名 讨论 帮助
登录 注册
编号 题目 状态 分数 总时间 内存 代码 / 答案文件 提交者 提交时间
#49241 #1257. 车 Accepted 100 114 ms 2536 K C++ 17 / 2.5 K 丁丁跑卡车 2021-06-06 15:08:12
显示原始代码 
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
#define ud unsigned int
#define ll long long
#define ull unsigned long long
#define MAX_INF 0x3f
#define MAX_INF_VAL 0x3f3f3f3f
#define MAX_INF_VAL_LL 0x3f3f3f3f3f3f3f3f
//#define pi 3.141592653589
#define eps 1e-9
#define F(x) ((x) / 3 + ((x) % 3 == 1 ? 0 : tb))
#define G(x) ((x) < tb ? (x)*3 + 1 : ((x)-tb) * 3 + 2)
//#define p 2173412051LL
//#define sz 2

using namespace std;

template <typename T>
void read(T &x) {
    x = 0;
    char ch = getchar();
    ll f = 1;
    while (!isdigit(ch)) {
        if (ch == '-')
            f *= -1;
        ch = getchar();
    }
    while (isdigit(ch)) {
        x = x * 10 + ch - 48;
        ch = getchar();
    }
    x *= f;
}

struct custom_hash {
    static uint64_t splitmix64(uint64_t x) {
        x += 0x9e3779b97f4a7c15;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
        return x ^ (x >> 31);
    }

    size_t operator()(uint64_t x) const {
        static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
        return splitmix64(x + FIXED_RANDOM);
    }
};

int ans;
bool vis[1010][1010];
bool s[1010][1010];
set<int> r[1010], c[1010];

void dfs(int, int);

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    int n, m;
    int x, y;
    cin >> n >> m;
    while (m--) {
        cin >> x >> y;
        s[x][y] = true;
        r[x].insert(y);
        c[y].insert(x);
    }
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= n; ++j) {
            if (s[i][j] && !vis[i][j]) {
                vis[i][j] = true;
                dfs(i, j);
            }
        }
    }
    cout << ans;
    return 0;
}

void dfs(int x, int y) {
    {
        int nx = x;
        auto it = r[x].upper_bound(y);
        if (it != r[x].end()) {
            int ny = *it;
            if (!vis[nx][ny]) {
                ++ans;
                vis[nx][ny] = true;
                dfs(nx, ny);
            }
        }
    }
    {
        int nx = x;
        auto it = r[x].lower_bound(y);
        if (it != r[x].begin()) {
            int ny = *(--it);
            if (!vis[nx][ny]) {
                ++ans;
                vis[nx][ny] = true;
                dfs(nx, ny);
            }
        }
    }
    {
        int ny = y;
        auto it = c[y].upper_bound(x);
        if (it != c[y].end()) {
            int nx = *it;
            if (!vis[nx][ny]) {
                ++ans;
                vis[nx][ny] = true;
                dfs(nx, ny);
            }
        }
    }
    {
        int ny = y;
        auto it = c[y].lower_bound(x);
        if (it != c[y].begin()) {
            int nx = *(--it);
            if (!vis[nx][ny]) {
                ++ans;
                vis[nx][ny] = true;
                dfs(nx, ny);
            }
        }
    }
}
子任务 #1
Accepted
得分：100
测试点 #1
Accepted
得分：100
用时：2 ms
内存：376 KiB

输入文件（01.in） 

8 3
1 1
1 8
8 8

答案文件（01.out） 

2

用户输出 

2

系统信息 

Exited with return code 0
测试点 #2
Accepted
得分：100
用时：2 ms
内存：376 KiB

输入文件（02.in） 

8 4
1 1
1 8
8 8
8 1

答案文件（02.out） 

3

用户输出 

3

系统信息 

Exited with return code 0
测试点 #3
Accepted
得分：100
用时：2 ms
内存：376 KiB

输入文件（03.in） 

5 5
1 1
2 2
3 3
4 4
5 5

答案文件（03.out） 

0

用户输出 

0

系统信息 

Exited with return code 0
测试点 #4
Accepted
得分：100
用时：2 ms
内存：376 KiB

输入文件（04.in） 

100 1
100 100

答案文件（04.out） 

0

用户输出 

0

系统信息 

Exited with return code 0
测试点 #5
Accepted
得分：100
用时：2 ms
内存：376 KiB

输入文件（05.in） 

10 12
1 2
1 4
1 6
3 6
5 6
10 7
8 7
6 7
4 7
2 7
7 3
9 5

答案文件（05.out） 

8

用户输出 

8

系统信息 

Exited with return code 0
测试点 #6
Accepted
得分：100
用时：2 ms
内存：376 KiB

输入文件（006.in） 

9 12
2 3
5 8
9 7
9 9
1 2
7 8
9 1
3 3
2 9
4 4
4 6
1 6

答案文件（006.out） 

9

用户输出 

9

系统信息 

Exited with return code 0
测试点 #7
Accepted
得分：100
用时：2 ms
内存：376 KiB

输入文件（007.in） 

9 1
3 3

答案文件（007.out） 

0

用户输出 

0

系统信息 

Exited with return code 0
测试点 #8
Accepted
得分：100
用时：2 ms
内存：376 KiB

输入文件（008.in） 

9 13
7 6
9 6
2 3
8 7
9 7
6 4
2 7
8 8
9 8
1 8
4 6
7 4
1 4

答案文件（008.out） 

12

用户输出 

12

系统信息 

Exited with return code 0
测试点 #9
Accepted
得分：100
用时：2 ms
内存：376 KiB

输入文件（009.in） 

7 13
7 3
7 2
1 1
7 5
6 5
3 3
6 1
4 6
3 2
5 7
4 3
7 4
4 7

答案文件（009.out） 

12

用户输出 

12

系统信息 

Exited with return code 0
测试点 #10
Accepted
得分：100
用时：2 ms
内存：376 KiB

输入文件（010.in） 

5 18
2 5
5 4
3 4
1 5
5 3
1 2
4 3
2 4
5 1
4 5
4 2
3 5
5 5
2 3
2 1
1 1
1 3
3 1

答案文件（010.out） 

17

用户输出 

17

系统信息 

Exited with return code 0
测试点 #11
Accepted
得分：100
用时：2 ms
内存：376 KiB

输入文件（011.in） 

9 5
6 9
3 2
2 8
2 9
1 1

答案文件（011.out） 

2

用户输出 

2

系统信息 

Exited with return code 0
测试点 #12
Accepted
得分：100
用时：2 ms
内存：376 KiB

输入文件（012.in） 

7 18
6 7
4 1
2 4
1 2
4 5
7 6
3 1
1 6
1 4
6 5
6 6
3 3
3 2
5 2
5 7
2 7
5 4
5 1

答案文件（012.out） 

17

用户输出 

17

系统信息 

Exited with return code 0
测试点 #13
Accepted
得分：100
用时：2 ms
内存：376 KiB

输入文件（013.in） 

4 6
2 4
1 2
2 1
2 3
1 1
1 3

答案文件（013.out） 

5

用户输出 

5

系统信息 

Exited with return code 0
测试点 #14
Accepted
得分：100
用时：2 ms
内存：376 KiB

输入文件（014.in） 

8 17
8 3
7 8
2 2
6 3
6 2
5 2
3 2
2 3
1 8
3 8
6 8
6 5
3 4
4 4
3 7
7 1
5 4

答案文件（014.out） 

16

用户输出 

16

系统信息 

Exited with return code 0
测试点 #15
Accepted
得分：100
用时：2 ms
内存：376 KiB

输入文件（015.in） 

6 15
5 2
4 1
1 3
2 5
4 2
3 6
3 2
6 5
2 3
5 6
2 4
2 1
3 1
1 4
6 4

答案文件（015.out） 

14

用户输出 

14

系统信息 

Exited with return code 0
测试点 #16
Accepted
得分：100
用时：4 ms
内存：2040 KiB

输入文件（016.in） 

901 598
565 361
500 175
205 860
524 404
193 20
190 212
379 254
654 653
174 763
344 42
271 140
76 774
<4567 bytes omitted>

答案文件（016.out） 

330

用户输出 

330

系统信息 

Exited with return code 0
测试点 #17
Accepted
得分：100
用时：3 ms
内存：1400 KiB

输入文件（017.in） 

530 551
370 236
26 367
405 200
55 355
436 316
478 344
397 315
476 392
60 512
233 526
514 248
429 325
<4086 bytes omitted>

答案文件（017.out） 

396

用户输出 

396

系统信息 

Exited with return code 0
测试点 #18
Accepted
得分：100
用时：3 ms
内存：1016 KiB

输入文件（018.in） 

904 84
121 471
711 121
862 151
441 193
514 539
479 427
342 129
583 269
260 175
607 462
641 578
282 2
<560 bytes omitted>

答案文件（018.out） 

2

用户输出 

2

系统信息 

Exited with return code 0
测试点 #19
Accepted
得分：100
用时：2 ms
内存：1016 KiB

输入文件（019.in） 

322 197
178 243
39 189
83 306
293 89
254 60
223 82
96 176
262 302
276 15
135 248
265 232
63 281
179 
<1356 bytes omitted>

答案文件（019.out） 

91

用户输出 

91

系统信息 

Exited with return code 0
测试点 #20
Accepted
得分：100
用时：3 ms
内存：1528 KiB

输入文件（020.in） 

569 804
264 153
179 489
204 404
121 227
309 101
534 470
361 276
537 107
474 107
513 334
167 332
313 
<6023 bytes omitted>

答案文件（020.out） 

729

用户输出 

729

系统信息 

Exited with return code 0
测试点 #21
Accepted
得分：100
用时：2 ms
内存：988 KiB

输入文件（021.in） 

254 526
54 106
142 201
49 219
238 117
136 242
171 196
132 49
59 44
195 169
103 230
222 77
154 159
14
<3680 bytes omitted>

答案文件（021.out） 

511

用户输出 

511

系统信息 

Exited with return code 0
测试点 #22
Accepted
得分：100
用时：3 ms
内存：1016 KiB

输入文件（022.in） 

300 844
197 204
168 265
277 270
101 251
192 36
222 79
270 212
242 139
161 124
169 220
182 249
177 25
<6051 bytes omitted>

答案文件（022.out） 

839

用户输出 

839

系统信息 

Exited with return code 0
测试点 #23
Accepted
得分：100
用时：3 ms
内存：1400 KiB

输入文件（023.in） 

503 668
81 343
481 83
182 390
22 300
487 210
278 503
164 337
90 1
437 244
219 20
98 97
210 262
76 42
<5008 bytes omitted>

答案文件（023.out） 

577

用户输出 

577

系统信息 

Exited with return code 0
测试点 #24
Accepted
得分：100
用时：2 ms
内存：1016 KiB

输入文件（024.in） 

300 848
273 182
240 132
279 174
237 281
279 180
131 34
24 238
239 8
274 237
63 24
79 233
204 105
75 
<6055 bytes omitted>

答案文件（024.out） 

841

用户输出 

841

系统信息 

Exited with return code 0
测试点 #25
Accepted
得分：100
用时：2 ms
内存：760 KiB

输入文件（025.in） 

166 728
126 14
151 109
118 126
112 37
76 151
6 71
98 94
117 79
101 90
84 42
117 112
42 7
54 6
155 98
<4795 bytes omitted>

答案文件（025.out） 

727

用户输出 

727

系统信息 

Exited with return code 0
测试点 #26
Accepted
得分：100
用时：2 ms
内存：376 KiB

输入文件（026.in） 

1 1
1 1

答案文件（026.out） 

0

用户输出 

0

系统信息 

Exited with return code 0
测试点 #27
Accepted
得分：100
用时：2 ms
内存：376 KiB

输入文件（027.in） 

7 49
1 1
1 2
1 3
1 4
1 5
1 6
1 7
2 1
2 2
2 3
2 4
2 5
2 6
2 7
3 1
3 2
3 3
3 4
3 5
3 6
3 7
4 1
4 2
4 3
<101 bytes omitted>

答案文件（027.out） 

48

用户输出 

48

系统信息 

Exited with return code 0
测试点 #28
Accepted
得分：100
用时：2 ms
内存：376 KiB

输入文件（028.in） 

15 225
1 1
1 2
1 3
1 4
1 5
1 6
1 7
1 8
1 9
1 10
1 11
1 12
1 13
1 14
1 15
2 1
2 2
2 3
2 4
2 5
2 6
2 7
<987 bytes omitted>

答案文件（028.out） 

224

用户输出 

224

系统信息 

Exited with return code 0
测试点 #29
Accepted
得分：100
用时：2 ms
内存：504 KiB

输入文件（029.in） 

26 676
1 1
1 2
1 3
1 4
1 5
1 6
1 7
1 8
1 9
1 10
1 11
1 12
1 13
1 14
1 15
1 16
1 17
1 18
1 19
1 20
1 
<3495 bytes omitted>

答案文件（029.out） 

675

用户输出 

675

系统信息 

Exited with return code 0
测试点 #30
Accepted
得分：100
用时：2 ms
内存：632 KiB

输入文件（030.in） 

31 961
1 1
1 2
1 3
1 4
1 5
1 6
1 7
1 8
1 9
1 10
1 11
1 12
1 13
1 14
1 15
1 16
1 17
1 18
1 19
1 20
1 
<5115 bytes omitted>

答案文件（030.out） 

960

用户输出 

960

系统信息 

Exited with return code 0
测试点 #31
Accepted
得分：100
用时：3 ms
内存：1752 KiB

输入文件（031.in） 

666 999
1 1
1 2
2 2
4 3
3 4
4 4
5 5
6 5
6 6
7 7
8 7
7 8
9 9
9 10
10 10
12 11
11 12
12 12
13 13
14 13
<7576 bytes omitted>

答案文件（031.out） 

666

用户输出 

666

系统信息 

Exited with return code 0
测试点 #32
Accepted
得分：100
用时：3 ms
内存：1784 KiB

输入文件（032.in） 

666 999
2 1
1 2
2 2
4 3
3 4
4 4
5 5
6 5
6 6
8 7
7 8
8 8
9 9
10 9
9 10
12 11
11 12
12 12
13 13
14 13

<7576 bytes omitted>

答案文件（032.out） 

666

用户输出 

666

系统信息 

Exited with return code 0
测试点 #33
Accepted
得分：100
用时：3 ms
内存：1784 KiB

输入文件（033.in） 

666 999
2 1
1 2
2 2
3 3
4 3
4 4
6 5
5 6
6 6
7 7
7 8
8 8
9 9
10 9
10 10
11 11
11 12
12 12
13 13
14 13
<7576 bytes omitted>

答案文件（033.out） 

666

用户输出 

666

系统信息 

Exited with return code 0
测试点 #34
Accepted
得分：100
用时：3 ms
内存：1784 KiB

输入文件（034.in） 

666 999
2 1
1 2
2 2
3 3
4 3
3 4
5 5
6 5
5 6
8 7
7 8
8 8
9 9
10 9
10 10
11 11
11 12
12 12
13 13
14 13
<7575 bytes omitted>

答案文件（034.out） 

666

用户输出 

666

系统信息 

Exited with return code 0
测试点 #35
Accepted
得分：100
用时：3 ms
内存：1784 KiB

输入文件（035.in） 

666 999
2 1
1 2
2 2
3 3
3 4
4 4
5 5
6 5
6 6
7 7
7 8
8 8
9 9
10 9
10 10
11 11
11 12
12 12
13 13
14 13
<7576 bytes omitted>

答案文件（035.out） 

666

用户输出 

666

系统信息 

Exited with return code 0
测试点 #36
Accepted
得分：100
用时：3 ms
内存：1784 KiB

输入文件（036.in） 

666 999
1 1
1 2
2 2
3 3
4 3
4 4
5 5
5 6
6 6
7 7
8 7
8 8
9 9
10 9
9 10
11 11
11 12
12 12
14 13
13 14

<7575 bytes omitted>

答案文件（036.out） 

666

用户输出 

666

系统信息 

Exited with return code 0
测试点 #37
Accepted
得分：100
用时：3 ms
内存：1784 KiB

输入文件（037.in） 

666 999
1 1
2 1
2 2
3 3
3 4
4 4
6 5
5 6
6 6
7 7
8 7
8 8
9 9
10 9
10 10
11 11
12 11
12 12
13 13
14 13
<7577 bytes omitted>

答案文件（037.out） 

666

用户输出 

666

系统信息 

Exited with return code 0
测试点 #38
Accepted
得分：100
用时：3 ms
内存：1820 KiB

输入文件（038.in） 

666 999
1 1
2 1
1 2
3 3
4 3
3 4
5 5
5 6
6 6
7 7
7 8
8 8
9 9
10 9
10 10
11 11
12 11
11 12
13 13
13 14
<7575 bytes omitted>

答案文件（038.out） 

666

用户输出 

666

系统信息 

Exited with return code 0
测试点 #39
Accepted
得分：100
用时：3 ms
内存：1784 KiB

输入文件（039.in） 

666 999
2 1
1 2
2 2
3 3
4 3
3 4
5 5
5 6
6 6
8 7
7 8
8 8
9 9
10 9
10 10
11 11
12 11
12 12
13 13
14 13
<7576 bytes omitted>

答案文件（039.out） 

666

用户输出 

666

系统信息 

Exited with return code 0
测试点 #40
Accepted
得分：100
用时：3 ms
内存：1784 KiB

输入文件（040.in） 

666 999
2 1
1 2
2 2
3 3
4 3
3 4
5 5
6 5
5 6
7 7
8 7
7 8
9 9
10 9
9 10
12 11
11 12
12 12
13 13
13 14

<7575 bytes omitted>

答案文件（040.out） 

666

用户输出 

666

系统信息 

Exited with return code 0
测试点 #41
Accepted
得分：100
用时：2 ms
内存：376 KiB

输入文件（041.in） 

1 1
1 1

答案文件（041.out） 

0

用户输出 

0

系统信息 

Exited with return code 0
测试点 #42
Accepted
得分：100
用时：2 ms
内存：376 KiB

输入文件（042.in） 

10 10
1 5
2 5
3 5
4 5
5 5
6 5
7 5
8 5
9 5
10 5

答案文件（042.out） 

9

用户输出 

9

系统信息 

Exited with return code 0
测试点 #43
Accepted
得分：100
用时：2 ms
内存：376 KiB

输入文件（043.in） 

10 10
10 1
10 2
10 3
10 4
10 5
10 6
10 7
10 8
10 9
10 10

答案文件（043.out） 

9

用户输出 

9

系统信息 

Exited with return code 0
测试点 #44
Accepted
得分：100
用时：2 ms
内存：632 KiB

输入文件（044.in） 

100 100
1 55
2 55
3 55
4 55
5 55
6 55
7 55
8 55
9 55
10 55
11 55
12 55
13 55
14 55
15 55
16 55
17 55
<500 bytes omitted>

答案文件（044.out） 

99

用户输出 

99

系统信息 

Exited with return code 0
测试点 #45
Accepted
得分：100
用时：2 ms
内存：348 KiB

输入文件（045.in） 

100 100
81 1
81 2
81 3
81 4
81 5
81 6
81 7
81 8
81 9
81 10
81 11
81 12
81 13
81 14
81 15
81 16
81 17
<500 bytes omitted>

答案文件（045.out） 

99

用户输出 

99

系统信息 

Exited with return code 0
测试点 #46
Accepted
得分：100
用时：4 ms
内存：2536 KiB

输入文件（046.in） 

1000 1000
1 608
2 608
3 608
4 608
5 608
6 608
7 608
8 608
9 608
10 608
11 608
12 608
13 608
14 608
1
<7803 bytes omitted>

答案文件（046.out） 

999

用户输出 

999

系统信息 

Exited with return code 0
测试点 #47
Accepted
得分：100
用时：3 ms
内存：504 KiB

输入文件（047.in） 

1000 1000
485 1
485 2
485 3
485 4
485 5
485 6
485 7
485 8
485 9
485 10
485 11
485 12
485 13
485 14
4
<7803 bytes omitted>

答案文件（047.out） 

999

用户输出 

999

系统信息 

Exited with return code 0
XJTUOJ Powered by SYZOJ. | 鲁ICP备2020034929号