10871 2024. 04. 17 10:52:26 Ablablabla Évzáró cpp17 Elfogadva 100/100 195ms 29352 KiB
#include <bits/stdc++.h>

using namespace std;

typedef pair<int, int> pii;

vector<vector<pii>> csucsok;
vector<bool> bejart;
vector<int> ans;

void dfs(int akt, int d){
    while(!csucsok[akt].empty()){
        pii kovi = csucsok[akt][csucsok[akt].size() - 1];
        csucsok[akt].pop_back();

        if(bejart[kovi.second]) continue;

        bejart[kovi.second] = 1;
        ans[kovi.second] = d;

        dfs(kovi.first, d ^ 1);
        return;
    }
}

int main(){
    int n;
    cin >> n;

    vector<pii> pontok(n);
    vector<int> pontX, pontY;
    for(int i = 0; i < n; i++){
        cin >> pontok[i].first >> pontok[i].second;

        pontX.push_back(pontok[i].first);
        pontY.push_back(pontok[i].second);
    }

    sort(pontX.begin(), pontX.end());
    sort(pontY.begin(), pontY.end());

    pontX.erase(unique(pontX.begin(), pontX.end()), pontX.end());
    pontY.erase(unique(pontY.begin(), pontY.end()), pontY.end());

    csucsok.assign(2 * n, vector<pii>());
    for(int i = 0; i < n; i++){
        pontok[i].first = lower_bound(pontX.begin(), pontX.end(), pontok[i].first) - pontX.begin();
        pontok[i].second = lower_bound(pontY.begin(), pontY.end(), pontok[i].second) - pontY.begin();
        pontok[i].second += n;

        csucsok[pontok[i].first].push_back({pontok[i].second, i});
        csucsok[pontok[i].second].push_back({pontok[i].first, i});
    }

    bejart.assign(n, 0);
    ans.assign(n, 0);

    for(int i = 0; i < n; i++){
        int d = 0;
        while(!csucsok[i].empty()){
            dfs(i, d);
            d ^=1;
        }
    }

    for(int i = 0; i < n; i++){
        cout << (ans[i] ? "F" : "L");
    }
    cout << "\n";
}
Részfeladat Összpont Teszt Verdikt Idő Memória
subtask1 0/0
1 Elfogadva 3ms 1812 KiB
2 Elfogadva 148ms 20704 KiB
subtask2 5/5
3 Elfogadva 143ms 23236 KiB
4 Elfogadva 144ms 23452 KiB
subtask3 7/7
5 Elfogadva 143ms 23236 KiB
6 Elfogadva 144ms 23452 KiB
7 Elfogadva 156ms 23932 KiB
8 Elfogadva 158ms 24588 KiB
9 Elfogadva 173ms 24768 KiB
10 Elfogadva 195ms 28308 KiB
subtask4 20/20
11 Elfogadva 186ms 22452 KiB
12 Elfogadva 182ms 22664 KiB
13 Elfogadva 182ms 22636 KiB
14 Elfogadva 178ms 22860 KiB
15 Elfogadva 174ms 23548 KiB
16 Elfogadva 181ms 29352 KiB
subtask5 13/13
17 Elfogadva 3ms 3764 KiB
18 Elfogadva 3ms 3768 KiB
19 Elfogadva 2ms 3764 KiB
20 Elfogadva 2ms 3764 KiB
21 Elfogadva 2ms 3768 KiB
22 Elfogadva 2ms 3776 KiB
23 Elfogadva 2ms 3692 KiB
24 Elfogadva 3ms 3688 KiB
25 Elfogadva 3ms 3940 KiB
26 Elfogadva 3ms 3900 KiB
27 Elfogadva 3ms 3908 KiB
28 Elfogadva 3ms 3932 KiB
29 Elfogadva 3ms 4020 KiB
30 Elfogadva 3ms 3904 KiB
31 Elfogadva 3ms 4148 KiB
32 Elfogadva 3ms 4232 KiB
33 Elfogadva 3ms 4116 KiB
subtask6 20/20
34 Elfogadva 3ms 3764 KiB
35 Elfogadva 3ms 3768 KiB
36 Elfogadva 2ms 3764 KiB
37 Elfogadva 2ms 3764 KiB
38 Elfogadva 2ms 3768 KiB
39 Elfogadva 2ms 3776 KiB
40 Elfogadva 2ms 3692 KiB
41 Elfogadva 3ms 3688 KiB
42 Elfogadva 3ms 3940 KiB
43 Elfogadva 3ms 3900 KiB
44 Elfogadva 3ms 3908 KiB
45 Elfogadva 3ms 3932 KiB
46 Elfogadva 3ms 4020 KiB
47 Elfogadva 3ms 3904 KiB
48 Elfogadva 3ms 4148 KiB
49 Elfogadva 3ms 4232 KiB
50 Elfogadva 3ms 4116 KiB
51 Elfogadva 4ms 4476 KiB
52 Elfogadva 4ms 4436 KiB
53 Elfogadva 4ms 4428 KiB
54 Elfogadva 4ms 4432 KiB
55 Elfogadva 4ms 4440 KiB
56 Elfogadva 4ms 4436 KiB
57 Elfogadva 4ms 4448 KiB
58 Elfogadva 4ms 4460 KiB
59 Elfogadva 4ms 4464 KiB
60 Elfogadva 4ms 4484 KiB
61 Elfogadva 4ms 4468 KiB
62 Elfogadva 4ms 4468 KiB
63 Elfogadva 4ms 4476 KiB
64 Elfogadva 4ms 4460 KiB
65 Elfogadva 4ms 4616 KiB
subtask7 35/35
66 Elfogadva 3ms 3764 KiB
67 Elfogadva 148ms 23056 KiB
68 Elfogadva 143ms 23236 KiB
69 Elfogadva 144ms 23452 KiB
70 Elfogadva 156ms 23932 KiB
71 Elfogadva 158ms 24588 KiB
72 Elfogadva 173ms 24768 KiB
73 Elfogadva 195ms 28308 KiB
74 Elfogadva 186ms 22452 KiB
75 Elfogadva 182ms 22664 KiB
76 Elfogadva 182ms 22636 KiB
77 Elfogadva 178ms 22860 KiB
78 Elfogadva 174ms 23548 KiB
79 Elfogadva 181ms 29352 KiB
80 Elfogadva 3ms 3768 KiB
81 Elfogadva 2ms 3764 KiB
82 Elfogadva 2ms 3764 KiB
83 Elfogadva 2ms 3768 KiB
84 Elfogadva 2ms 3776 KiB
85 Elfogadva 2ms 3692 KiB
86 Elfogadva 3ms 3688 KiB
87 Elfogadva 3ms 3940 KiB
88 Elfogadva 3ms 3900 KiB
89 Elfogadva 3ms 3908 KiB
90 Elfogadva 3ms 3932 KiB
91 Elfogadva 3ms 4020 KiB
92 Elfogadva 3ms 3904 KiB
93 Elfogadva 3ms 4148 KiB
94 Elfogadva 3ms 4232 KiB
95 Elfogadva 3ms 4116 KiB
96 Elfogadva 4ms 4476 KiB
97 Elfogadva 4ms 4436 KiB
98 Elfogadva 4ms 4428 KiB
99 Elfogadva 4ms 4432 KiB
100 Elfogadva 4ms 4440 KiB
101 Elfogadva 4ms 4436 KiB
102 Elfogadva 4ms 4448 KiB
103 Elfogadva 4ms 4460 KiB
104 Elfogadva 4ms 4464 KiB
105 Elfogadva 4ms 4484 KiB
106 Elfogadva 4ms 4468 KiB
107 Elfogadva 4ms 4468 KiB
108 Elfogadva 4ms 4476 KiB
109 Elfogadva 4ms 4460 KiB
110 Elfogadva 4ms 4616 KiB
111 Elfogadva 136ms 21624 KiB
112 Elfogadva 129ms 22500 KiB
113 Elfogadva 129ms 22496 KiB
114 Elfogadva 136ms 22660 KiB
115 Elfogadva 134ms 22664 KiB
116 Elfogadva 136ms 22660 KiB
117 Elfogadva 140ms 22016 KiB
118 Elfogadva 136ms 22664 KiB
119 Elfogadva 140ms 22796 KiB
120 Elfogadva 142ms 22124 KiB
121 Elfogadva 138ms 23184 KiB