109622024-04-21 14:04:39k_balintÉvzárócpp17Hibás válasz 32/100203ms101556 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ÖsszpontTesztVerdiktIdőMemória
subtask10/0
1Elfogadva20ms39480 KiB
2Hibás válasz111ms62404 KiB
subtask25/5
3Elfogadva136ms79924 KiB
4Elfogadva137ms80224 KiB
subtask37/7
5Elfogadva136ms79924 KiB
6Elfogadva137ms80224 KiB
7Elfogadva149ms80812 KiB
8Elfogadva155ms81216 KiB
9Elfogadva170ms82044 KiB
10Elfogadva203ms100908 KiB
subtask420/20
11Elfogadva148ms59904 KiB
12Elfogadva146ms57960 KiB
13Elfogadva138ms57820 KiB
14Elfogadva136ms58200 KiB
15Elfogadva141ms58888 KiB
16Elfogadva197ms101556 KiB
subtask50/13
17Elfogadva17ms41368 KiB
18Elfogadva17ms41580 KiB
19Elfogadva20ms41664 KiB
20Elfogadva20ms41664 KiB
21Elfogadva19ms41664 KiB
22Elfogadva19ms41792 KiB
23Elfogadva19ms41760 KiB
24Elfogadva17ms41984 KiB
25Elfogadva19ms41972 KiB
26Elfogadva19ms41980 KiB
27Elfogadva19ms42064 KiB
28Elfogadva19ms41972 KiB
29Elfogadva19ms42088 KiB
30Elfogadva19ms42212 KiB
31Hibás válasz19ms42188 KiB
32Hibás válasz19ms42332 KiB
33Hibás válasz19ms42256 KiB
subtask60/20
34Elfogadva17ms41368 KiB
35Elfogadva17ms41580 KiB
36Elfogadva20ms41664 KiB
37Elfogadva20ms41664 KiB
38Elfogadva19ms41664 KiB
39Elfogadva19ms41792 KiB
40Elfogadva19ms41760 KiB
41Elfogadva17ms41984 KiB
42Elfogadva19ms41972 KiB
43Elfogadva19ms41980 KiB
44Elfogadva19ms42064 KiB
45Elfogadva19ms41972 KiB
46Elfogadva19ms42088 KiB
47Elfogadva19ms42212 KiB
48Hibás válasz19ms42188 KiB
49Hibás válasz19ms42332 KiB
50Hibás válasz19ms42256 KiB
51Elfogadva20ms42484 KiB
52Elfogadva20ms42348 KiB
53Elfogadva20ms42352 KiB
54Elfogadva20ms42480 KiB
55Hibás válasz20ms42620 KiB
56Hibás válasz20ms42496 KiB
57Elfogadva20ms42516 KiB
58Hibás válasz20ms42508 KiB
59Hibás válasz20ms42508 KiB
60Hibás válasz20ms42744 KiB
61Elfogadva20ms42732 KiB
62Hibás válasz20ms42776 KiB
63Hibás válasz18ms42876 KiB
64Hibás válasz17ms42896 KiB
65Hibás válasz20ms42880 KiB
subtask70/35
66Elfogadva17ms41368 KiB
67Hibás válasz111ms65244 KiB
68Elfogadva136ms79924 KiB
69Elfogadva137ms80224 KiB
70Elfogadva149ms80812 KiB
71Elfogadva155ms81216 KiB
72Elfogadva170ms82044 KiB
73Elfogadva203ms100908 KiB
74Elfogadva148ms59904 KiB
75Elfogadva146ms57960 KiB
76Elfogadva138ms57820 KiB
77Elfogadva136ms58200 KiB
78Elfogadva141ms58888 KiB
79Elfogadva197ms101556 KiB
80Elfogadva17ms41580 KiB
81Elfogadva20ms41664 KiB
82Elfogadva20ms41664 KiB
83Elfogadva19ms41664 KiB
84Elfogadva19ms41792 KiB
85Elfogadva19ms41760 KiB
86Elfogadva17ms41984 KiB
87Elfogadva19ms41972 KiB
88Elfogadva19ms41980 KiB
89Elfogadva19ms42064 KiB
90Elfogadva19ms41972 KiB
91Elfogadva19ms42088 KiB
92Elfogadva19ms42212 KiB
93Hibás válasz19ms42188 KiB
94Hibás válasz19ms42332 KiB
95Hibás válasz19ms42256 KiB
96Elfogadva20ms42484 KiB
97Elfogadva20ms42348 KiB
98Elfogadva20ms42352 KiB
99Elfogadva20ms42480 KiB
100Hibás válasz20ms42620 KiB
101Hibás válasz20ms42496 KiB
102Elfogadva20ms42516 KiB
103Hibás válasz20ms42508 KiB
104Hibás válasz20ms42508 KiB
105Hibás válasz20ms42744 KiB
106Elfogadva20ms42732 KiB
107Hibás válasz20ms42776 KiB
108Hibás válasz18ms42876 KiB
109Hibás válasz17ms42896 KiB
110Hibás válasz20ms42880 KiB
111Elfogadva90ms62808 KiB
112Elfogadva86ms63856 KiB
113Elfogadva86ms63820 KiB
114Elfogadva90ms64368 KiB
115Hibás válasz97ms64268 KiB
116Hibás válasz98ms64356 KiB
117Hibás válasz101ms63356 KiB
118Hibás válasz93ms63940 KiB
119Hibás válasz103ms64468 KiB
120Hibás válasz101ms64008 KiB
121Hibás válasz92ms64488 KiB