10961 2024. 04. 21 14:03:17 k_balint Évzáró cpp17 Hibás válasz 5/100 136ms 52500 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 Összpont Teszt Verdikt Idő Memória
subtask1 0/0
1 Elfogadva 6ms 11336 KiB
2 Hibás válasz 93ms 34204 KiB
subtask2 5/5
3 Elfogadva 111ms 51388 KiB
4 Elfogadva 122ms 51616 KiB
subtask3 0/7
5 Elfogadva 111ms 51388 KiB
6 Elfogadva 122ms 51616 KiB
7 Futási hiba 122ms 52080 KiB
8 Futási hiba 115ms 52500 KiB
9 Futási hiba 128ms 47168 KiB
10 Futási hiba 136ms 33876 KiB
subtask4 0/20
11 Elfogadva 136ms 31796 KiB
12 Elfogadva 130ms 30048 KiB
13 Elfogadva 133ms 29788 KiB
14 Elfogadva 134ms 30148 KiB
15 Elfogadva 128ms 30612 KiB
16 Futási hiba 126ms 34104 KiB
subtask5 0/13
17 Elfogadva 7ms 13148 KiB
18 Elfogadva 6ms 13172 KiB
19 Elfogadva 6ms 13104 KiB
20 Elfogadva 6ms 13236 KiB
21 Elfogadva 6ms 13444 KiB
22 Elfogadva 6ms 13660 KiB
23 Elfogadva 6ms 13768 KiB
24 Elfogadva 6ms 13876 KiB
25 Elfogadva 7ms 13964 KiB
26 Elfogadva 7ms 14088 KiB
27 Elfogadva 7ms 14128 KiB
28 Elfogadva 7ms 14208 KiB
29 Elfogadva 7ms 14324 KiB
30 Elfogadva 7ms 14204 KiB
31 Hibás válasz 7ms 14212 KiB
32 Hibás válasz 7ms 14208 KiB
33 Hibás válasz 6ms 14208 KiB
subtask6 0/20
34 Elfogadva 7ms 13148 KiB
35 Elfogadva 6ms 13172 KiB
36 Elfogadva 6ms 13104 KiB
37 Elfogadva 6ms 13236 KiB
38 Elfogadva 6ms 13444 KiB
39 Elfogadva 6ms 13660 KiB
40 Elfogadva 6ms 13768 KiB
41 Elfogadva 6ms 13876 KiB
42 Elfogadva 7ms 13964 KiB
43 Elfogadva 7ms 14088 KiB
44 Elfogadva 7ms 14128 KiB
45 Elfogadva 7ms 14208 KiB
46 Elfogadva 7ms 14324 KiB
47 Elfogadva 7ms 14204 KiB
48 Hibás válasz 7ms 14212 KiB
49 Hibás válasz 7ms 14208 KiB
50 Hibás válasz 6ms 14208 KiB
51 Elfogadva 7ms 14292 KiB
52 Elfogadva 7ms 14316 KiB
53 Elfogadva 7ms 14472 KiB
54 Elfogadva 7ms 14300 KiB
55 Hibás válasz 7ms 14452 KiB
56 Hibás válasz 6ms 14436 KiB
57 Elfogadva 8ms 14432 KiB
58 Hibás válasz 7ms 14320 KiB
59 Hibás válasz 7ms 14584 KiB
60 Hibás válasz 7ms 14680 KiB
61 Elfogadva 7ms 14684 KiB
62 Hibás válasz 7ms 14696 KiB
63 Hibás válasz 7ms 14660 KiB
64 Hibás válasz 8ms 14828 KiB
65 Hibás válasz 8ms 14812 KiB
subtask7 0/35
66 Elfogadva 7ms 13148 KiB
67 Hibás válasz 97ms 37172 KiB
68 Elfogadva 111ms 51388 KiB
69 Elfogadva 122ms 51616 KiB
70 Futási hiba 122ms 52080 KiB
71 Futási hiba 115ms 52500 KiB
72 Futási hiba 128ms 47168 KiB
73 Futási hiba 136ms 33876 KiB
74 Elfogadva 136ms 31796 KiB
75 Elfogadva 130ms 30048 KiB
76 Elfogadva 133ms 29788 KiB
77 Elfogadva 134ms 30148 KiB
78 Elfogadva 128ms 30612 KiB
79 Futási hiba 126ms 34104 KiB
80 Elfogadva 6ms 13172 KiB
81 Elfogadva 6ms 13104 KiB
82 Elfogadva 6ms 13236 KiB
83 Elfogadva 6ms 13444 KiB
84 Elfogadva 6ms 13660 KiB
85 Elfogadva 6ms 13768 KiB
86 Elfogadva 6ms 13876 KiB
87 Elfogadva 7ms 13964 KiB
88 Elfogadva 7ms 14088 KiB
89 Elfogadva 7ms 14128 KiB
90 Elfogadva 7ms 14208 KiB
91 Elfogadva 7ms 14324 KiB
92 Elfogadva 7ms 14204 KiB
93 Hibás válasz 7ms 14212 KiB
94 Hibás válasz 7ms 14208 KiB
95 Hibás válasz 6ms 14208 KiB
96 Elfogadva 7ms 14292 KiB
97 Elfogadva 7ms 14316 KiB
98 Elfogadva 7ms 14472 KiB
99 Elfogadva 7ms 14300 KiB
100 Hibás válasz 7ms 14452 KiB
101 Hibás válasz 6ms 14436 KiB
102 Elfogadva 8ms 14432 KiB
103 Hibás válasz 7ms 14320 KiB
104 Hibás válasz 7ms 14584 KiB
105 Hibás válasz 7ms 14680 KiB
106 Elfogadva 7ms 14684 KiB
107 Hibás válasz 7ms 14696 KiB
108 Hibás válasz 7ms 14660 KiB
109 Hibás válasz 8ms 14828 KiB
110 Hibás válasz 8ms 14812 KiB
111 Elfogadva 82ms 34616 KiB
112 Elfogadva 79ms 35624 KiB
113 Elfogadva 76ms 35628 KiB
114 Elfogadva 82ms 36144 KiB
115 Hibás válasz 82ms 36012 KiB
116 Hibás válasz 85ms 36120 KiB
117 Hibás válasz 87ms 35308 KiB
118 Hibás válasz 83ms 35712 KiB
119 Hibás válasz 87ms 36212 KiB
120 Hibás válasz 90ms 35700 KiB
121 Hibás válasz 83ms 36216 KiB