QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#726723 | #3612. All in the Family | nickbelov# | WA | 1ms | 3676kb | C++20 | 4.4kb | 2024-11-09 07:04:46 | 2024-11-09 07:04:48 |
Judging History
answer
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;
template<typename T>
ostream_iterator<T> oit(const string &s = " "){ return ostream_iterator<T>(cout,s.c_str()); }
inline auto rep(int l, int r) { return views::iota(min(l, r), r); }
inline auto rep(int n) { return rep(0, n); }
inline auto rep1(int l, int r) { return rep(l, r + 1); }
inline auto rep1(int n) { return rep(1, n + 1); }
inline auto per(int l, int r) { return rep(l, r) | views::reverse; }
inline auto per(int n) { return per(0, n); }
inline auto per1(int l, int r) { return per(l, r + 1); }
inline auto per1(int n) { return per(1, n + 1); }
#define A(a) begin(a),end(a)
inline auto len = ranges::ssize;
struct chash {
static uint64_t splitmix64(uint64_t x) {
// http://xorshift.di.unimi.it/splitmix64.c
x += 0x9e3779b97f4a7c15;
x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
return x ^ (x >> 31);
}
size_t operator()(uint64_t x) const {
static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
return splitmix64(x + FIXED_RANDOM);
}
};
template<typename T, typename U> using pb_map = gp_hash_table<T, U, chash>;
template<typename T> using pb_set = gp_hash_table<T, null_type, chash>;
#define K first
#define V second
using ll = long long;
using ld = long double;
using vi = vector<int>;
using vii = vector<vector<int>>;
typedef vector<ll> vll;
using pll = pair<ll,ll>;
using pii = pair<int,int>;
constexpr ll NN = 2e5, M = 1000000007, L = 20;
void run()
{
int t,q; cin >> t >> q; int n = 100;
vii adj(n); vi in_deg(n);
map<string,int> mp1; map<int,string> mp2; int idx=0;
auto get = [&](const string &s){
if(mp1.contains(s)) return mp1[s];
mp1[s]=idx,mp2[idx]=s;
idx++;
return idx-1;
};
for(int i : rep(t)){
string p; cin >> p; int c; cin >> c;
int p_idx = get(p);
for(int j : rep(c)){
string s; cin >> s; int cidx = get(s);
in_deg[cidx]++;
adj[p_idx].push_back(cidx);
}
}
vector<pii> Q;
for(int i : rep(q)){
string a,b; cin >> a >> b;
Q.emplace_back(get(a),get(b));
}
vi dep(n),par(n,-1);
int root = 0; while(in_deg[root]) root++;
function<void(int)> dfs = [&](int i){
for(int j : adj[i])
dep[j]=dep[i]+1,par[j]=i,dfs(j);
}; dfs(root);
auto lca = [&](int u,int v){
if(dep[v] > dep[u]) swap(u,v);
while(dep[u] > dep[v]) u = par[u];
while(u != v)
u = par[u],v=par[v];
return u;
};
auto nth = [](int n){
string s = to_string(n);
if(n == 11 or n == 12 or n == 13) {s+="th"; return s;}
if(s.back()=='1') s += "st";
else if(s.back()=='2') s += "nd";
else if(s.back()=='3') s += "rd";
else s += "th";
return s;
};
for(auto [u,v] : Q){
int lc = lca(u,v);
if(dep[u] > dep[v]) swap(u,v); //wlog u is closer to lca than v
string a = mp2[u], b = mp2[v];
int m = dep[u]-dep[lc], n = dep[v]-dep[lc];
if(m==0){
if(n==1){
cout << b << " is the child of " << a << '\n';
}else{
string great = "";
string ans;
while(n-2 > 0) great += "great ", n--;
ans = b + " is the " + great + "grandchild of " + a;
cout << ans << '\n';
}
}else if(m==n){
if(n==1) cout << a << " and " << b << " are siblings\n";
else{
string ans;
ans = a + " and " + b + " are " + nth(n-1) + " cousins";
cout << ans << '\n';
}
}else if(m<n){
int diff = n-m;
string ans = a + " and " + b + " are " + nth(m-1) + " cousins, " + to_string(diff);
string time = " time"; if(diff>1) time+="s";
time += " ";
ans += time;
ans += "removed";
cout << ans << '\n';
}else assert(false);
}
}
int main()
{
//KING OF THE WORLD...... U.W.T.B
cin.tie(0);
ios_base::sync_with_stdio(false);
run();
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3580kb
input:
4 5 Horatio 1 Irene Chris 2 Gina Horatio Alice 3 Dan Emily Frank Bob 2 Alice Chris Irene Bob Dan Frank Chris Emily Alice Chris Dan Irene
output:
Irene is the great grandchild of Bob Dan and Frank are siblings Chris and Emily are 0th cousins, 1 time removed Alice and Chris are siblings Dan and Irene are 1st cousins, 1 time removed
result:
ok 5 lines
Test #2:
score: 0
Accepted
time: 1ms
memory: 3636kb
input:
4 6 A 4 B C D E H 3 I J K C 2 F G D 1 H G C H A F G F H F K B K
output:
G is the child of C H is the grandchild of A F and G are siblings F and H are 1st cousins F and K are 1st cousins, 1 time removed B and K are 0th cousins, 2 times removed
result:
ok 6 lines
Test #3:
score: -100
Wrong Answer
time: 1ms
memory: 3676kb
input:
13 12 A 2 P C P 1 B C 1 D D 1 E E 1 F F 1 G G 1 H H 1 I I 1 J J 1 K K 1 L L 1 M M 1 N B C B D B E B F B G B H B I B J B K B L B M B N
output:
C and B are 0th cousins, 1 time removed B and D are 1st cousins B and E are 1st cousins, 1 time removed B and F are 1st cousins, 2 times removed B and G are 1st cousins, 3 times removed B and H are 1st cousins, 4 times removed B and I are 1st cousins, 5 times removed B and J are 1st cousins, 6 times...
result:
wrong answer 1st lines differ - expected: 'B and C are 0th cousins, 1 time removed', found: 'C and B are 0th cousins, 1 time removed'