2248 | 2023-01-05 19:06:48 | sztomi | Tom és Jerry 3 | cpp17 | Compilation error |
#include <bits/stdc++.h>
using namespace std;
struct irany_ut{
int pont;
int hossz;
irany_ut(int p=-1, int h=0) : pont(p), hossz(h) {}
};
struct comp{
bool operator()(irany_ut a, irany_ut b){
if(a.hossz == b.hossz)
return a.pont < b.pont;
return a.hossz > b.hossz;
}
};
int n, k;
vector<vector<int>> graf;
vector<int> tom_tav;
vector<int> jerry_tav;
// ket legtavolabbi az adott pontbol
vector<pair<irany_ut, irany_ut>> legtavolabbi;
void tavot_allit(int akt, int elozo, vector<int>& tavok){
for(int kov : graf[akt]){
if(kov == elozo) continue;
tavok[kov] = tavok[akt] + 1;
tavot_allit(kov, akt, tavok);
}
}
// csak a fa adott allasaban a pont alatt levo utakat veszi figyelembe
void legtavolabbit_allit_alatta(int akt, int elozo){
for(int kov : graf[akt]){
if(kov == elozo) continue;
legtavolabbit_allit_alatta(kov, akt);
set<irany_ut, comp> sorrend;
sorrend.insert(legtavolabbi[akt].first);
sorrend.insert(legtavolabbi[akt].second);
irany_ut ideigl(kov, legtavolabbi[kov].first.hossz+1);
sorrend.insert(ideigl);
legtavolabbi[akt].first = *sorrend.begin();
sorrend.erase(sorrend.begin());
legtavolabbi[akt].second = *sorrend.begin();
}
}
// az alatta levo leghosszabbak segitsegevel kiszamolja a felette levo utakbol is a leghosszabbakat
void legtavolabbit_allit(int akt, int elozo){
if(elozo != -1){
set<irany_ut, comp> sorrend;
sorrend.insert(legtavolabbi[akt].first);
sorrend.insert(legtavolabbi[akt].second);
irany_ut ideigl;
if(legtavolabbi[elozo].first.pont == akt){
ideigl = irany_ut(elozo, legtavolabbi[elozo].second.hossz+1);
}
else{
ideigl = irany_ut(elozo, legtavolabbi[elozo].first.hossz+1);
}
sorrend.insert(ideigl);
legtavolabbi[akt].first = *sorrend.begin();
sorrend.erase(sorrend.begin());
legtavolabbi[akt].second = *sorrend.begin();
}
for(int kov : graf[akt]){
if(kov == elozo) continue;
legtavolabbit_allit(kov, akt);
}
}
void megold(){
int tom_kezd, jerry_kezd;
cin >> n >> tom_kezd >> jerry_kezd >> k;
graf.assign(n+1, vector<int>());
tom_tav.assign(n+1, -1);
jerry_tav.assign(n+1, -1);
legtavolabbi.assign(n+1, {irany_ut(), irany_ut()});
int a, b;
for(int i = 0; i < n-1; i++){
cin >> a >> b;
graf[a].push_back(b);
graf[b].push_back(a);
}
tom_tav[tom_kezd] = 0;
tavot_allit(tom_kezd, -1, tom_tav);
jerry_tav[jerry_kezd] = 0;
tavot_allit(jerry_kezd, -1, jerry_tav);
// ha Tom rogton kezdes utan elkapja Jerryt
if(tom_tav[jerry_kezd] <= 1){
cout << "IGEN\n";
return;
}
// eloszor az alatta levokbol a ket legtavolabbit beallitjuk az osszesnek
// utana, meg az egyestol odavezeto uton a felette levok kozul a nem felejuk meno agbol allitjak be
// jo lenne tudni, hogy egy adott pontbol egy szomszedja fele indulva mennyi a leghosszabb ut
// akkor, amikor nezzuk egy masik szomszedjat
legtavolabbit_allit_alatta(1, -1);
legtavolabbit_allit(1, -1);
/*
for(int i = 1; i <= n; i++){
cout << "pont: " << i << " ------------\n";
cout << "elso: pont " << legtavolabbi[i].first.pont << " hossz " << legtavolabbi[i].first.hossz << "\n";
cout << "masodik: pont " << legtavolabbi[i].second.pont << " masodik " << legtavolabbi[i].second.hossz << "\n";
cout << "jerry tav: " << jerry_tav[i] << "\n";
cout << "tom tav: " << tom_tav[i] << "\n";
}
*/
if(2*k+1 > n-1){
cout << "IGEN\n";
return;
}
bool tom_elkapja = true;
for(int i = 1; i <= n; i++){
// ha el elkapna Tom Jerryt egy adott pontban
if(tom_tav[i]-1 <= jerry_tav[i]) continue;
// ha Jerry egy megfeleloen hosszu utra jut
if(legtavolabbi[i].first.hossz + legtavolabbi[i].second.hossz >= 2*k+1){
tom_elkapja = false;
}
}
cout << (tom_elkapja ? "IGEN" : "NEM") << "\n";
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(NULL);
int t;
cin >> t;
while(t--){
megold();
}
}
exit status 1
In file included from /usr/include/c++/11/map:60,
from /usr/include/x86_64-linux-gnu/c++/11/bits/stdc++.h:81,
from main.cpp:1:
/usr/include/c++/11/bits/stl_tree.h: In instantiation of 'static const _Key& std::_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::_S_key(std::_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::_Const_Link_type) [with _Key = irany_ut; _Val = irany_ut; _KeyOfValue = std::_Identity<irany_ut>; _Compare = comp; _Alloc = std::allocator<irany_ut>; std::_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::_Const_Link_type = const std::_Rb_tree_node<irany_ut>*]':
/usr/include/c++/11/bits/stl_tree.h:2071:47: required from 'std::pair<std::_Rb_tree_node_base*, std::_Rb_tree_node_base*> std::_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::_M_get_insert_unique_pos(const key_type&) [with _Key = irany_ut; _Val = irany_ut; _KeyOfValue = std::_Identity<irany_ut>; _Compare = comp; _Alloc = std::allocator<irany_ut>; std::_Rb_tree<_Key, _Val, _KeyOfValue, _...