108652024-04-17 08:54:17AblablablaÉvzárócpp17Futási hiba 33/100178ms131908 KiB
#include <bits/stdc++.h>

using namespace std;

typedef pair<int, int> pii;

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

void dfs(int akt, bool fiu){
    while(!csucsok[akt].empty()){
        pii kovi = csucsok[akt].front();
        csucsok[akt].pop();

        if(bejart[kovi.second]) continue;

        bejart[kovi.second] = 1;
        ans[kovi.second] = fiu;
        dfs(kovi.first, !fiu);
        return;
    }
}

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

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

        pontX[i] = pontok[i].first;
        pontY[i] = 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(3 * n, queue<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();

        csucsok[pontok[i].first].push({pontok[i].second + n, i});
        csucsok[pontok[i].second + n].push({pontok[i].first, i});
    }

    /*for(int i = 0; i < n; i++){
        cout << pontok[i].first << " " << pontok[i].second << "\n";
    }*/

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

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

    for(bool x : ans){
        cout << (x ? "F" : "L");
    }
    cout << "\n";
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
subtask10/0
1Elfogadva3ms1888 KiB
2Futási hiba165ms131908 KiB
subtask20/5
3Futási hiba168ms131664 KiB
4Futási hiba172ms131428 KiB
subtask30/7
5Futási hiba168ms131664 KiB
6Futási hiba172ms131428 KiB
7Futási hiba174ms131148 KiB
8Futási hiba177ms131108 KiB
9Futási hiba178ms130868 KiB
10Futási hiba166ms130624 KiB
subtask40/20
11Futási hiba178ms130480 KiB
12Futási hiba178ms130248 KiB
13Futási hiba165ms130024 KiB
14Futási hiba165ms129796 KiB
15Futási hiba178ms129792 KiB
16Futási hiba178ms129792 KiB
subtask513/13
17Elfogadva3ms4292 KiB
18Elfogadva3ms4300 KiB
19Elfogadva3ms4512 KiB
20Elfogadva3ms4520 KiB
21Elfogadva3ms4600 KiB
22Elfogadva3ms4688 KiB
23Elfogadva3ms4760 KiB
24Elfogadva3ms4684 KiB
25Elfogadva3ms4732 KiB
26Elfogadva3ms4588 KiB
27Elfogadva3ms4668 KiB
28Elfogadva3ms4800 KiB
29Elfogadva3ms4928 KiB
30Elfogadva3ms5016 KiB
31Elfogadva3ms5000 KiB
32Elfogadva3ms5008 KiB
33Elfogadva3ms5140 KiB
subtask620/20
34Elfogadva3ms4292 KiB
35Elfogadva3ms4300 KiB
36Elfogadva3ms4512 KiB
37Elfogadva3ms4520 KiB
38Elfogadva3ms4600 KiB
39Elfogadva3ms4688 KiB
40Elfogadva3ms4760 KiB
41Elfogadva3ms4684 KiB
42Elfogadva3ms4732 KiB
43Elfogadva3ms4588 KiB
44Elfogadva3ms4668 KiB
45Elfogadva3ms4800 KiB
46Elfogadva3ms4928 KiB
47Elfogadva3ms5016 KiB
48Elfogadva3ms5000 KiB
49Elfogadva3ms5008 KiB
50Elfogadva3ms5140 KiB
51Elfogadva6ms8904 KiB
52Elfogadva6ms8900 KiB
53Elfogadva6ms9016 KiB
54Elfogadva6ms8892 KiB
55Elfogadva6ms8896 KiB
56Elfogadva6ms9004 KiB
57Elfogadva6ms8904 KiB
58Elfogadva6ms8976 KiB
59Elfogadva6ms8996 KiB
60Elfogadva4ms9116 KiB
61Elfogadva4ms9200 KiB
62Elfogadva4ms9072 KiB
63Elfogadva6ms9196 KiB
64Elfogadva4ms9192 KiB
65Elfogadva4ms9324 KiB
subtask70/35
66Elfogadva3ms4292 KiB
67Futási hiba162ms128700 KiB
68Futási hiba168ms131664 KiB
69Futási hiba172ms131428 KiB
70Futási hiba174ms131148 KiB
71Futási hiba177ms131108 KiB
72Futási hiba178ms130868 KiB
73Futási hiba166ms130624 KiB
74Futási hiba178ms130480 KiB
75Futási hiba178ms130248 KiB
76Futási hiba165ms130024 KiB
77Futási hiba165ms129796 KiB
78Futási hiba178ms129792 KiB
79Futási hiba178ms129792 KiB
80Elfogadva3ms4300 KiB
81Elfogadva3ms4512 KiB
82Elfogadva3ms4520 KiB
83Elfogadva3ms4600 KiB
84Elfogadva3ms4688 KiB
85Elfogadva3ms4760 KiB
86Elfogadva3ms4684 KiB
87Elfogadva3ms4732 KiB
88Elfogadva3ms4588 KiB
89Elfogadva3ms4668 KiB
90Elfogadva3ms4800 KiB
91Elfogadva3ms4928 KiB
92Elfogadva3ms5016 KiB
93Elfogadva3ms5000 KiB
94Elfogadva3ms5008 KiB
95Elfogadva3ms5140 KiB
96Elfogadva6ms8904 KiB
97Elfogadva6ms8900 KiB
98Elfogadva6ms9016 KiB
99Elfogadva6ms8892 KiB
100Elfogadva6ms8896 KiB
101Elfogadva6ms9004 KiB
102Elfogadva6ms8904 KiB
103Elfogadva6ms8976 KiB
104Elfogadva6ms8996 KiB
105Elfogadva4ms9116 KiB
106Elfogadva4ms9200 KiB
107Elfogadva4ms9072 KiB
108Elfogadva6ms9196 KiB
109Elfogadva4ms9192 KiB
110Elfogadva4ms9324 KiB
111Futási hiba158ms128672 KiB
112Futási hiba153ms128644 KiB
113Futási hiba156ms128596 KiB
114Futási hiba162ms128612 KiB
115Futási hiba170ms128604 KiB
116Futási hiba159ms128596 KiB
117Futási hiba159ms128596 KiB
118Futási hiba171ms128592 KiB
119Futási hiba172ms128572 KiB
120Futási hiba172ms128588 KiB
121Futási hiba156ms128588 KiB