QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#726723#3612. All in the Familynickbelov#WA 1ms3676kbC++204.4kb2024-11-09 07:04:462024-11-09 07:04:48

Judging History

This is the latest submission verdict.

  • [2024-11-09 07:04:48]
  • Judged
  • Verdict: WA
  • Time: 1ms
  • Memory: 3676kb
  • [2024-11-09 07:04:46]
  • Submitted

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'