10963 2024. 04. 21 14:13:16 k_balint Évzáró cpp17 Elfogadva 100/100 221ms 84476 KiB
#include <bits/stdc++.h>
using namespace std;
const int c=8e5+5;

vector<int> compx;
vector<int> compy;

int fx(int k){
    return lower_bound(compx.begin(),compx.end(),k)-compx.begin() + 1;
}

int fy(int k){
    return lower_bound(compy.begin(),compy.end(),k)-compy.begin() + 1 + compx.size();
}

int n,N;
vector<pair<int,int>> adj[c];
bool volt[c];
int idx[c];
bool ans[c], vis[c], deg[c];
vector<pair<int,int>> edg;

void dfs(int v){
    vis[v]=1;
    while(idx[v]<adj[v].size()){
        int x=idx[v];
        int id=adj[v][x].second;
        if(volt[id]){
            ++idx[v];
            continue;
        }
        volt[id]=1;
        ++idx[v];
        if(v<=compx.size()) ans[id]=1;
        else ans[id]=0;
        dfs(adj[v][x].first);
    }
}


int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    cin>>n;
    for(int i=1;i<=n;i++){
        int a,b; cin>>a>>b;
        edg.push_back(make_pair(a,b));
        compx.push_back(a);
        compy.push_back(b);
    }

    sort(compx.begin(),compx.end());
    compx.resize(unique(compx.begin(),compx.end())-compx.begin());

    sort(compy.begin(),compy.end());
    compy.resize(unique(compy.begin(),compy.end())-compy.begin());

    N=compx.size()+compy.size();

    for(int i=0;i<n;i++){
        int a=fx(edg[i].first);
        int b=fy(edg[i].second);
        adj[a].push_back(make_pair(b,i));
        adj[b].push_back(make_pair(a,i));
        deg[a]^=1; deg[b]^=1;
    }

    int m=n;
    int p=-1;
    for(int i=1;i<=N;i++){
        if(deg[i]){
            if(p==-1) p=i;
            else{
                adj[i].push_back(make_pair(p,m));
                adj[p].push_back(make_pair(i,m++));
                p=-1;
            }
        }
    }

    for(int i=1;i<=N;i++){
        if(!vis[i]) dfs(i);
    }

    for(int i=0;i<n;i++){
        if(ans[i]) cout << "L";
        else cout << "F";
    }
}
Részfeladat Összpont Teszt Verdikt Idő Memória
subtask1 0/0
1 Elfogadva 17ms 39480 KiB
2 Elfogadva 104ms 61876 KiB
subtask2 5/5
3 Elfogadva 115ms 71516 KiB
4 Elfogadva 130ms 71760 KiB
subtask3 7/7
5 Elfogadva 115ms 71516 KiB
6 Elfogadva 130ms 71760 KiB
7 Elfogadva 127ms 72288 KiB
8 Elfogadva 146ms 72840 KiB
9 Elfogadva 158ms 73600 KiB
10 Elfogadva 221ms 84476 KiB
subtask4 20/20
11 Elfogadva 148ms 60240 KiB
12 Elfogadva 145ms 58372 KiB
13 Elfogadva 144ms 58504 KiB
14 Elfogadva 143ms 58860 KiB
15 Elfogadva 141ms 58820 KiB
16 Elfogadva 186ms 75904 KiB
subtask5 13/13
17 Elfogadva 19ms 41676 KiB
18 Elfogadva 17ms 41892 KiB
19 Elfogadva 19ms 42104 KiB
20 Elfogadva 17ms 42184 KiB
21 Elfogadva 16ms 42188 KiB
22 Elfogadva 19ms 42184 KiB
23 Elfogadva 17ms 42412 KiB
24 Elfogadva 16ms 42620 KiB
25 Elfogadva 16ms 42612 KiB
26 Elfogadva 19ms 42612 KiB
27 Elfogadva 19ms 42396 KiB
28 Elfogadva 19ms 42404 KiB
29 Elfogadva 17ms 42396 KiB
30 Elfogadva 19ms 42492 KiB
31 Elfogadva 19ms 42496 KiB
32 Elfogadva 19ms 42400 KiB
33 Elfogadva 19ms 42408 KiB
subtask6 20/20
34 Elfogadva 19ms 41676 KiB
35 Elfogadva 17ms 41892 KiB
36 Elfogadva 19ms 42104 KiB
37 Elfogadva 17ms 42184 KiB
38 Elfogadva 16ms 42188 KiB
39 Elfogadva 19ms 42184 KiB
40 Elfogadva 17ms 42412 KiB
41 Elfogadva 16ms 42620 KiB
42 Elfogadva 16ms 42612 KiB
43 Elfogadva 19ms 42612 KiB
44 Elfogadva 19ms 42396 KiB
45 Elfogadva 19ms 42404 KiB
46 Elfogadva 17ms 42396 KiB
47 Elfogadva 19ms 42492 KiB
48 Elfogadva 19ms 42496 KiB
49 Elfogadva 19ms 42400 KiB
50 Elfogadva 19ms 42408 KiB
51 Elfogadva 21ms 42624 KiB
52 Elfogadva 18ms 42616 KiB
53 Elfogadva 17ms 42612 KiB
54 Elfogadva 20ms 42504 KiB
55 Elfogadva 20ms 42644 KiB
56 Elfogadva 20ms 42740 KiB
57 Elfogadva 17ms 42736 KiB
58 Elfogadva 17ms 42740 KiB
59 Elfogadva 20ms 42864 KiB
60 Elfogadva 20ms 42860 KiB
61 Elfogadva 17ms 42656 KiB
62 Elfogadva 20ms 42752 KiB
63 Elfogadva 17ms 42748 KiB
64 Elfogadva 17ms 42656 KiB
65 Elfogadva 21ms 42652 KiB
subtask7 35/35
66 Elfogadva 19ms 41676 KiB
67 Elfogadva 104ms 64620 KiB
68 Elfogadva 115ms 71516 KiB
69 Elfogadva 130ms 71760 KiB
70 Elfogadva 127ms 72288 KiB
71 Elfogadva 146ms 72840 KiB
72 Elfogadva 158ms 73600 KiB
73 Elfogadva 221ms 84476 KiB
74 Elfogadva 148ms 60240 KiB
75 Elfogadva 145ms 58372 KiB
76 Elfogadva 144ms 58504 KiB
77 Elfogadva 143ms 58860 KiB
78 Elfogadva 141ms 58820 KiB
79 Elfogadva 186ms 75904 KiB
80 Elfogadva 17ms 41892 KiB
81 Elfogadva 19ms 42104 KiB
82 Elfogadva 17ms 42184 KiB
83 Elfogadva 16ms 42188 KiB
84 Elfogadva 19ms 42184 KiB
85 Elfogadva 17ms 42412 KiB
86 Elfogadva 16ms 42620 KiB
87 Elfogadva 16ms 42612 KiB
88 Elfogadva 19ms 42612 KiB
89 Elfogadva 19ms 42396 KiB
90 Elfogadva 19ms 42404 KiB
91 Elfogadva 17ms 42396 KiB
92 Elfogadva 19ms 42492 KiB
93 Elfogadva 19ms 42496 KiB
94 Elfogadva 19ms 42400 KiB
95 Elfogadva 19ms 42408 KiB
96 Elfogadva 21ms 42624 KiB
97 Elfogadva 18ms 42616 KiB
98 Elfogadva 17ms 42612 KiB
99 Elfogadva 20ms 42504 KiB
100 Elfogadva 20ms 42644 KiB
101 Elfogadva 20ms 42740 KiB
102 Elfogadva 17ms 42736 KiB
103 Elfogadva 17ms 42740 KiB
104 Elfogadva 20ms 42864 KiB
105 Elfogadva 20ms 42860 KiB
106 Elfogadva 17ms 42656 KiB
107 Elfogadva 20ms 42752 KiB
108 Elfogadva 17ms 42748 KiB
109 Elfogadva 17ms 42656 KiB
110 Elfogadva 21ms 42652 KiB
111 Elfogadva 97ms 62604 KiB
112 Elfogadva 93ms 63648 KiB
113 Elfogadva 93ms 63608 KiB
114 Elfogadva 92ms 64524 KiB
115 Elfogadva 97ms 63936 KiB
116 Elfogadva 94ms 64328 KiB
117 Elfogadva 97ms 63184 KiB
118 Elfogadva 90ms 63708 KiB
119 Elfogadva 96ms 64264 KiB
120 Elfogadva 105ms 63732 KiB
121 Elfogadva 93ms 64340 KiB