109612024-04-21 14:03:17k_balintÉvzárócpp17Hibás válasz 5/100136ms52500 KiB
#include <bits/stdc++.h>
using namespace std;
const int c=2e5+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
1Elfogadva6ms11336 KiB
2Hibás válasz93ms34204 KiB
subtask25/5
3Elfogadva111ms51388 KiB
4Elfogadva122ms51616 KiB
subtask30/7
5Elfogadva111ms51388 KiB
6Elfogadva122ms51616 KiB
7Futási hiba122ms52080 KiB
8Futási hiba115ms52500 KiB
9Futási hiba128ms47168 KiB
10Futási hiba136ms33876 KiB
subtask40/20
11Elfogadva136ms31796 KiB
12Elfogadva130ms30048 KiB
13Elfogadva133ms29788 KiB
14Elfogadva134ms30148 KiB
15Elfogadva128ms30612 KiB
16Futási hiba126ms34104 KiB
subtask50/13
17Elfogadva7ms13148 KiB
18Elfogadva6ms13172 KiB
19Elfogadva6ms13104 KiB
20Elfogadva6ms13236 KiB
21Elfogadva6ms13444 KiB
22Elfogadva6ms13660 KiB
23Elfogadva6ms13768 KiB
24Elfogadva6ms13876 KiB
25Elfogadva7ms13964 KiB
26Elfogadva7ms14088 KiB
27Elfogadva7ms14128 KiB
28Elfogadva7ms14208 KiB
29Elfogadva7ms14324 KiB
30Elfogadva7ms14204 KiB
31Hibás válasz7ms14212 KiB
32Hibás válasz7ms14208 KiB
33Hibás válasz6ms14208 KiB
subtask60/20
34Elfogadva7ms13148 KiB
35Elfogadva6ms13172 KiB
36Elfogadva6ms13104 KiB
37Elfogadva6ms13236 KiB
38Elfogadva6ms13444 KiB
39Elfogadva6ms13660 KiB
40Elfogadva6ms13768 KiB
41Elfogadva6ms13876 KiB
42Elfogadva7ms13964 KiB
43Elfogadva7ms14088 KiB
44Elfogadva7ms14128 KiB
45Elfogadva7ms14208 KiB
46Elfogadva7ms14324 KiB
47Elfogadva7ms14204 KiB
48Hibás válasz7ms14212 KiB
49Hibás válasz7ms14208 KiB
50Hibás válasz6ms14208 KiB
51Elfogadva7ms14292 KiB
52Elfogadva7ms14316 KiB
53Elfogadva7ms14472 KiB
54Elfogadva7ms14300 KiB
55Hibás válasz7ms14452 KiB
56Hibás válasz6ms14436 KiB
57Elfogadva8ms14432 KiB
58Hibás válasz7ms14320 KiB
59Hibás válasz7ms14584 KiB
60Hibás válasz7ms14680 KiB
61Elfogadva7ms14684 KiB
62Hibás válasz7ms14696 KiB
63Hibás válasz7ms14660 KiB
64Hibás válasz8ms14828 KiB
65Hibás válasz8ms14812 KiB
subtask70/35
66Elfogadva7ms13148 KiB
67Hibás válasz97ms37172 KiB
68Elfogadva111ms51388 KiB
69Elfogadva122ms51616 KiB
70Futási hiba122ms52080 KiB
71Futási hiba115ms52500 KiB
72Futási hiba128ms47168 KiB
73Futási hiba136ms33876 KiB
74Elfogadva136ms31796 KiB
75Elfogadva130ms30048 KiB
76Elfogadva133ms29788 KiB
77Elfogadva134ms30148 KiB
78Elfogadva128ms30612 KiB
79Futási hiba126ms34104 KiB
80Elfogadva6ms13172 KiB
81Elfogadva6ms13104 KiB
82Elfogadva6ms13236 KiB
83Elfogadva6ms13444 KiB
84Elfogadva6ms13660 KiB
85Elfogadva6ms13768 KiB
86Elfogadva6ms13876 KiB
87Elfogadva7ms13964 KiB
88Elfogadva7ms14088 KiB
89Elfogadva7ms14128 KiB
90Elfogadva7ms14208 KiB
91Elfogadva7ms14324 KiB
92Elfogadva7ms14204 KiB
93Hibás válasz7ms14212 KiB
94Hibás válasz7ms14208 KiB
95Hibás válasz6ms14208 KiB
96Elfogadva7ms14292 KiB
97Elfogadva7ms14316 KiB
98Elfogadva7ms14472 KiB
99Elfogadva7ms14300 KiB
100Hibás válasz7ms14452 KiB
101Hibás válasz6ms14436 KiB
102Elfogadva8ms14432 KiB
103Hibás válasz7ms14320 KiB
104Hibás válasz7ms14584 KiB
105Hibás válasz7ms14680 KiB
106Elfogadva7ms14684 KiB
107Hibás válasz7ms14696 KiB
108Hibás válasz7ms14660 KiB
109Hibás válasz8ms14828 KiB
110Hibás válasz8ms14812 KiB
111Elfogadva82ms34616 KiB
112Elfogadva79ms35624 KiB
113Elfogadva76ms35628 KiB
114Elfogadva82ms36144 KiB
115Hibás válasz82ms36012 KiB
116Hibás válasz85ms36120 KiB
117Hibás válasz87ms35308 KiB
118Hibás válasz83ms35712 KiB
119Hibás válasz87ms36212 KiB
120Hibás válasz90ms35700 KiB
121Hibás válasz83ms36216 KiB