10962 2024. 04. 21 14:04:39 k_balint Évzáró cpp17 Hibás válasz 32/100 203ms 101556 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++));
            }
        }
    }

    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 20ms 39480 KiB
2 Hibás válasz 111ms 62404 KiB
subtask2 5/5
3 Elfogadva 136ms 79924 KiB
4 Elfogadva 137ms 80224 KiB
subtask3 7/7
5 Elfogadva 136ms 79924 KiB
6 Elfogadva 137ms 80224 KiB
7 Elfogadva 149ms 80812 KiB
8 Elfogadva 155ms 81216 KiB
9 Elfogadva 170ms 82044 KiB
10 Elfogadva 203ms 100908 KiB
subtask4 20/20
11 Elfogadva 148ms 59904 KiB
12 Elfogadva 146ms 57960 KiB
13 Elfogadva 138ms 57820 KiB
14 Elfogadva 136ms 58200 KiB
15 Elfogadva 141ms 58888 KiB
16 Elfogadva 197ms 101556 KiB
subtask5 0/13
17 Elfogadva 17ms 41368 KiB
18 Elfogadva 17ms 41580 KiB
19 Elfogadva 20ms 41664 KiB
20 Elfogadva 20ms 41664 KiB
21 Elfogadva 19ms 41664 KiB
22 Elfogadva 19ms 41792 KiB
23 Elfogadva 19ms 41760 KiB
24 Elfogadva 17ms 41984 KiB
25 Elfogadva 19ms 41972 KiB
26 Elfogadva 19ms 41980 KiB
27 Elfogadva 19ms 42064 KiB
28 Elfogadva 19ms 41972 KiB
29 Elfogadva 19ms 42088 KiB
30 Elfogadva 19ms 42212 KiB
31 Hibás válasz 19ms 42188 KiB
32 Hibás válasz 19ms 42332 KiB
33 Hibás válasz 19ms 42256 KiB
subtask6 0/20
34 Elfogadva 17ms 41368 KiB
35 Elfogadva 17ms 41580 KiB
36 Elfogadva 20ms 41664 KiB
37 Elfogadva 20ms 41664 KiB
38 Elfogadva 19ms 41664 KiB
39 Elfogadva 19ms 41792 KiB
40 Elfogadva 19ms 41760 KiB
41 Elfogadva 17ms 41984 KiB
42 Elfogadva 19ms 41972 KiB
43 Elfogadva 19ms 41980 KiB
44 Elfogadva 19ms 42064 KiB
45 Elfogadva 19ms 41972 KiB
46 Elfogadva 19ms 42088 KiB
47 Elfogadva 19ms 42212 KiB
48 Hibás válasz 19ms 42188 KiB
49 Hibás válasz 19ms 42332 KiB
50 Hibás válasz 19ms 42256 KiB
51 Elfogadva 20ms 42484 KiB
52 Elfogadva 20ms 42348 KiB
53 Elfogadva 20ms 42352 KiB
54 Elfogadva 20ms 42480 KiB
55 Hibás válasz 20ms 42620 KiB
56 Hibás válasz 20ms 42496 KiB
57 Elfogadva 20ms 42516 KiB
58 Hibás válasz 20ms 42508 KiB
59 Hibás válasz 20ms 42508 KiB
60 Hibás válasz 20ms 42744 KiB
61 Elfogadva 20ms 42732 KiB
62 Hibás válasz 20ms 42776 KiB
63 Hibás válasz 18ms 42876 KiB
64 Hibás válasz 17ms 42896 KiB
65 Hibás válasz 20ms 42880 KiB
subtask7 0/35
66 Elfogadva 17ms 41368 KiB
67 Hibás válasz 111ms 65244 KiB
68 Elfogadva 136ms 79924 KiB
69 Elfogadva 137ms 80224 KiB
70 Elfogadva 149ms 80812 KiB
71 Elfogadva 155ms 81216 KiB
72 Elfogadva 170ms 82044 KiB
73 Elfogadva 203ms 100908 KiB
74 Elfogadva 148ms 59904 KiB
75 Elfogadva 146ms 57960 KiB
76 Elfogadva 138ms 57820 KiB
77 Elfogadva 136ms 58200 KiB
78 Elfogadva 141ms 58888 KiB
79 Elfogadva 197ms 101556 KiB
80 Elfogadva 17ms 41580 KiB
81 Elfogadva 20ms 41664 KiB
82 Elfogadva 20ms 41664 KiB
83 Elfogadva 19ms 41664 KiB
84 Elfogadva 19ms 41792 KiB
85 Elfogadva 19ms 41760 KiB
86 Elfogadva 17ms 41984 KiB
87 Elfogadva 19ms 41972 KiB
88 Elfogadva 19ms 41980 KiB
89 Elfogadva 19ms 42064 KiB
90 Elfogadva 19ms 41972 KiB
91 Elfogadva 19ms 42088 KiB
92 Elfogadva 19ms 42212 KiB
93 Hibás válasz 19ms 42188 KiB
94 Hibás válasz 19ms 42332 KiB
95 Hibás válasz 19ms 42256 KiB
96 Elfogadva 20ms 42484 KiB
97 Elfogadva 20ms 42348 KiB
98 Elfogadva 20ms 42352 KiB
99 Elfogadva 20ms 42480 KiB
100 Hibás válasz 20ms 42620 KiB
101 Hibás válasz 20ms 42496 KiB
102 Elfogadva 20ms 42516 KiB
103 Hibás válasz 20ms 42508 KiB
104 Hibás válasz 20ms 42508 KiB
105 Hibás válasz 20ms 42744 KiB
106 Elfogadva 20ms 42732 KiB
107 Hibás válasz 20ms 42776 KiB
108 Hibás válasz 18ms 42876 KiB
109 Hibás válasz 17ms 42896 KiB
110 Hibás válasz 20ms 42880 KiB
111 Elfogadva 90ms 62808 KiB
112 Elfogadva 86ms 63856 KiB
113 Elfogadva 86ms 63820 KiB
114 Elfogadva 90ms 64368 KiB
115 Hibás válasz 97ms 64268 KiB
116 Hibás válasz 98ms 64356 KiB
117 Hibás válasz 101ms 63356 KiB
118 Hibás válasz 93ms 63940 KiB
119 Hibás válasz 103ms 64468 KiB
120 Hibás válasz 101ms 64008 KiB
121 Hibás válasz 92ms 64488 KiB