108712024-04-17 10:52:26AblablablaÉvzárócpp17Elfogadva 100/100195ms29352 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ÖsszpontTesztVerdiktIdőMemória
subtask10/0
1Elfogadva3ms1812 KiB
2Elfogadva148ms20704 KiB
subtask25/5
3Elfogadva143ms23236 KiB
4Elfogadva144ms23452 KiB
subtask37/7
5Elfogadva143ms23236 KiB
6Elfogadva144ms23452 KiB
7Elfogadva156ms23932 KiB
8Elfogadva158ms24588 KiB
9Elfogadva173ms24768 KiB
10Elfogadva195ms28308 KiB
subtask420/20
11Elfogadva186ms22452 KiB
12Elfogadva182ms22664 KiB
13Elfogadva182ms22636 KiB
14Elfogadva178ms22860 KiB
15Elfogadva174ms23548 KiB
16Elfogadva181ms29352 KiB
subtask513/13
17Elfogadva3ms3764 KiB
18Elfogadva3ms3768 KiB
19Elfogadva2ms3764 KiB
20Elfogadva2ms3764 KiB
21Elfogadva2ms3768 KiB
22Elfogadva2ms3776 KiB
23Elfogadva2ms3692 KiB
24Elfogadva3ms3688 KiB
25Elfogadva3ms3940 KiB
26Elfogadva3ms3900 KiB
27Elfogadva3ms3908 KiB
28Elfogadva3ms3932 KiB
29Elfogadva3ms4020 KiB
30Elfogadva3ms3904 KiB
31Elfogadva3ms4148 KiB
32Elfogadva3ms4232 KiB
33Elfogadva3ms4116 KiB
subtask620/20
34Elfogadva3ms3764 KiB
35Elfogadva3ms3768 KiB
36Elfogadva2ms3764 KiB
37Elfogadva2ms3764 KiB
38Elfogadva2ms3768 KiB
39Elfogadva2ms3776 KiB
40Elfogadva2ms3692 KiB
41Elfogadva3ms3688 KiB
42Elfogadva3ms3940 KiB
43Elfogadva3ms3900 KiB
44Elfogadva3ms3908 KiB
45Elfogadva3ms3932 KiB
46Elfogadva3ms4020 KiB
47Elfogadva3ms3904 KiB
48Elfogadva3ms4148 KiB
49Elfogadva3ms4232 KiB
50Elfogadva3ms4116 KiB
51Elfogadva4ms4476 KiB
52Elfogadva4ms4436 KiB
53Elfogadva4ms4428 KiB
54Elfogadva4ms4432 KiB
55Elfogadva4ms4440 KiB
56Elfogadva4ms4436 KiB
57Elfogadva4ms4448 KiB
58Elfogadva4ms4460 KiB
59Elfogadva4ms4464 KiB
60Elfogadva4ms4484 KiB
61Elfogadva4ms4468 KiB
62Elfogadva4ms4468 KiB
63Elfogadva4ms4476 KiB
64Elfogadva4ms4460 KiB
65Elfogadva4ms4616 KiB
subtask735/35
66Elfogadva3ms3764 KiB
67Elfogadva148ms23056 KiB
68Elfogadva143ms23236 KiB
69Elfogadva144ms23452 KiB
70Elfogadva156ms23932 KiB
71Elfogadva158ms24588 KiB
72Elfogadva173ms24768 KiB
73Elfogadva195ms28308 KiB
74Elfogadva186ms22452 KiB
75Elfogadva182ms22664 KiB
76Elfogadva182ms22636 KiB
77Elfogadva178ms22860 KiB
78Elfogadva174ms23548 KiB
79Elfogadva181ms29352 KiB
80Elfogadva3ms3768 KiB
81Elfogadva2ms3764 KiB
82Elfogadva2ms3764 KiB
83Elfogadva2ms3768 KiB
84Elfogadva2ms3776 KiB
85Elfogadva2ms3692 KiB
86Elfogadva3ms3688 KiB
87Elfogadva3ms3940 KiB
88Elfogadva3ms3900 KiB
89Elfogadva3ms3908 KiB
90Elfogadva3ms3932 KiB
91Elfogadva3ms4020 KiB
92Elfogadva3ms3904 KiB
93Elfogadva3ms4148 KiB
94Elfogadva3ms4232 KiB
95Elfogadva3ms4116 KiB
96Elfogadva4ms4476 KiB
97Elfogadva4ms4436 KiB
98Elfogadva4ms4428 KiB
99Elfogadva4ms4432 KiB
100Elfogadva4ms4440 KiB
101Elfogadva4ms4436 KiB
102Elfogadva4ms4448 KiB
103Elfogadva4ms4460 KiB
104Elfogadva4ms4464 KiB
105Elfogadva4ms4484 KiB
106Elfogadva4ms4468 KiB
107Elfogadva4ms4468 KiB
108Elfogadva4ms4476 KiB
109Elfogadva4ms4460 KiB
110Elfogadva4ms4616 KiB
111Elfogadva136ms21624 KiB
112Elfogadva129ms22500 KiB
113Elfogadva129ms22496 KiB
114Elfogadva136ms22660 KiB
115Elfogadva134ms22664 KiB
116Elfogadva136ms22660 KiB
117Elfogadva140ms22016 KiB
118Elfogadva136ms22664 KiB
119Elfogadva140ms22796 KiB
120Elfogadva142ms22124 KiB
121Elfogadva138ms23184 KiB