ამოხსნების სტატუსი

ამ გვერდზე თქვენ იხილავთ გაგზავნილი ამოხსნების სტატუსს.


გაგზავნის თარიღი: 20.06.2020 17:22:13

ამოცანა: კომუნიკაციის სისტემა

მომხმარებელი: qartveli

ვერდიქტი: სრული ამოხსნა

შეფასება: 100.0 ქულა







#include <iostream>
#include <vector>

using namespace std;

inline int distanceSquared(int x1, int y1, int x2, int y2) {
    return (x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2);
}

vector<int> x, y, dist;

inline bool isAdjacent(int i, int j) {
    return distanceSquared(x[i], y[i], x[j], y[j]) <= dist[i] * dist[i];
}

vector< vector<int> > adj; // neighbours / adjacency list
vector<bool> used;
int dfs(int i) {
    used[i] = true;
    int total = 1;
    for (int j : adj[i]) {
        if (!used[j]) total += dfs(j);
    }
    return total;
}

int main() {
    int n; cin >> n;
    x.resize(n), y.resize(n), dist.resize(n), adj.resize(n);
    for (int i = 0; i < n; ++i) {
        cin >> x[i] >> y[i] >> dist[i];
    }

    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            if (i != j && isAdjacent(i, j)) adj[i].push_back(j);
        }
    }

    int most = 0;
    for (int i = 0; i < n; ++i) {
        used = vector<bool>(n);
        int current = dfs(i);
        if (current > most) most = current;
    }
    cout << most << endl;

    return 0;
}

ტესტები

შემავალი მონაცემები
4
1 3 5
5 4 3
7 2 1
6 1 1
გამომავალი მონაცემები
3
თქვენი პასუხი
3
ჩეკერის პასუხი
YES
შემავალი მონაცემები
200
13339 17934 324
13549 13893 908
11442 20504 1208
2904 913 1175
7302 14944 1103
1004 361 1662
1101 14526 922
12327 7050 382
3939 16796 953
13445 11311 1847
14680 16002 388
16032 4552 771
17203 7346 391
3560 10250 2027
11252 17553 1987
3440 18557 2161
11...
გამომავალი მონაცემები
25
თქვენი პასუხი
25
ჩეკერის პასუხი
YES
შემავალი მონაცემები
40
14383 5886 199
11915 22793 2239
10386 10492 445
16421 2362 4109
18690 20059 1623
13926 5540 1640
14172 5736 1481
20368 2567 4509
15782 21530 4080
15123 24067 2431
13929 4802 5036
23058 8069 3065
11393 18456 1059
3042 1229 1623
9421 19919 1880
23537 198 ...
გამომავალი მონაცემები
8
თქვენი პასუხი
8
ჩეკერის პასუხი
YES
შემავალი მონაცემები
60
8440 19729 3974
8117 13097 3445
9481 15675 3101
23927 4567 3283
4497 22353 3646
1965 5306 3177
6219 3624 1103
7871 5732 1696
9503 5019 1647
13368 9708 1201
1340 18149 3853
723 17618 4061
22846 18451 2038
18555 17379 2353
12764 13228 238
17350 15193 2964...
გამომავალი მონაცემები
10
თქვენი პასუხი
10
ჩეკერის პასუხი
YES
შემავალი მონაცემები
80
22090 2684 123
5542 5936 700
17445 19756 2086
18418 6887 497
3348 7172 3435
12009 2336 608
16342 17587 2685
19301 22713 1836
321 1255 1085
19599 17721 3422
5939 14811 776
15667 11705 3018
11127 4150 3387
21658 13920 2512
2422 17269 1703
4081 20630 995
4...
გამომავალი მონაცემები
15
თქვენი პასუხი
15
ჩეკერის პასუხი
YES
შემავალი მონაცემები
100
5857 18627 806
11886 14214 1441
18512 20090 3033
9479 9610 766
16189 2274 824
22641 6620 1314
23987 2888 3010
24566 12770 1864
6856 15417 897
22260 849 602
7205 23059 2141
23518 9945 132
11873 3458 1406
17637 4289 1843
1607 20478 3180
24314 9471 840
16...
გამომავალი მონაცემები
13
თქვენი პასუხი
13
ჩეკერის პასუხი
YES
შემავალი მონაცემები
130
15000 8378 2430
20053 5081 199
21338 5989 1471
3067 10147 1134
1787 7231 2784
17122 16281 2403
9850 15179 2377
2254 15350 1940
23813 17857 2769
24181 21081 953
15720 2433 1733
15181 22487 2127
4296 18825 697
13722 21892 1009
5297 15032 1851
18181 23506...
გამომავალი მონაცემები
15
თქვენი პასუხი
15
ჩეკერის პასუხი
YES
შემავალი მონაცემები
150
7339 7464 810
12330 12086 2213
6349 19915 748
18881 20011 2582
24133 4387 2
23287 6773 1823
6519 11742 2416
15244 3124 101
16259 2063 1470
11353 6712 1497
8705 5404 1053
1799 17734 2303
24315 15435 2301
15853 669 372
16487 24802 799
20562 23089 326
102...
გამომავალი მონაცემები
13
თქვენი პასუხი
13
ჩეკერის პასუხი
YES
შემავალი მონაცემები
175
8793 23439 1641
21620 20114 1951
7371 3418 216
13534 19883 24
23567 4697 360
16067 3674 815
22433 10490 1377
12132 15949 269
10523 6690 12
13147 7629 1589
17335 16422 2180
21968 13043 455
339 11766 1345
10936 16653 1060
2052 15220 1117
19204 6287 1863
...
გამომავალი მონაცემები
15
თქვენი პასუხი
15
ჩეკერის პასუხი
YES
შემავალი მონაცემები
190
14401 12945 133
1394 7366 1574
13589 5456 105
12795 24826 654
8803 18860 1516
8882 3155 89
11648 10695 452
12505 22946 2132
24067 8863 1852
23790 3408 2060
5768 9161 633
24093 10555 1769
11251 24144 2226
12651 3291 872
10435 3447 1450
275 3681 1872
172...
გამომავალი მონაცემები
18
თქვენი პასუხი
18
ჩეკერის პასუხი
YES