QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#639386#9459. Tree Equationucup-team5234AC ✓411ms14988kbC++206.1kb2024-10-13 19:16:162024-10-13 19:16:16

Judging History

This is the latest submission verdict.

  • [2024-10-13 19:16:16]
  • Judged
  • Verdict: AC
  • Time: 411ms
  • Memory: 14988kb
Show
  • [2024-10-13 19:16:16]
  • Submitted

answer

#include <bits/stdc++.h>
using namespace std;
#define all(v) (v).begin(),(v).end()
#define pb(a) push_back(a)
#define rep(i, n) for(int i=0;i<n;i++)
#define foa(e, v) for(auto&& e : v)
using ll = long long;
const ll MOD7 = 1000000007, MOD998 = 998244353, INF = (1LL << 60);
#define dout(a) cout<<fixed<<setprecision(10)<<a<<endl;


void solve() {
    int na, nb, nc;
    cin >> na >> nb >> nc;
    vector<vector<int>> va(na), vb(nb), vc(nc);
    vector<int> pc(nc);
    rep(i, na) {
        int x;
        cin >> x;
        x --;
        if(x != -1) va[x].pb(i);
    }
    rep(i, nb) {
        int x;
        cin >> x;
        x --;
        if(x != -1) vb[x].pb(i);
    }
    rep(i, nc) {
        int x;
        cin >> x;
        x --;
        if(x != -1) vc[x].pb(i);
        pc[i] = x;
    }

    auto distance = [&](vector<vector<int>> &v) -> vector<int> {
        vector<int> dis((int)v.size(), 1 << 30);
        auto dfs = [&](auto dfs, int now) -> void {
            foa(e, v[now]) {
                dis[e] = dis[now] + 1;
                dfs(dfs, e);
            }
        };
        dis[0] = 0;
        dfs(dfs, 0);
        return dis;
    };

    int id = 0;
    map<vector<int>, int> mp;
    vector<vector<int>> inv;
    auto tohash = [&](vector<vector<int>> &v) -> vector<int> {
        int m = v.size();
        vector<int> parhash(m, -1);
        auto dfs = [&](auto dfs, int now) -> int {
            vector<int> ret;
            foa(e, v[now]) {
                ret.pb(dfs(dfs, e));
            }
            sort(all(ret));
            if(!mp.count(ret)) {
                inv.push_back(ret);
                mp[ret] = id ++; 
            } 
            return parhash[now] = mp[ret];
        };
        dfs(dfs, 0);
        return parhash;
    };
    auto Chash = tohash(vc);
    auto Cdis = distance(vc);
    int dc = -1, idx = -1;
    rep(i, nc) {
        if(dc < Cdis[i]) {
            dc = Cdis[i];
            idx = i;
        }
    }

    auto i2p = [&](int x) -> vector<int> {
        vector<int> ret;
        auto dfs = [&](auto &&dfs, int now, int p) -> void {
            ret.pb(p);
            int j = ret.size();
            foa(e, inv[now]) {
                dfs(dfs, e, j);
            }
        };
        dfs(dfs, x, 0);
        return ret;
    };

    auto test2 = [&](vector<vector<int>> &v, int hs) -> int {
        auto p = i2p(hs);
        int n = p.size();
        rep(i, n) p[i] --;
        vector<vector<int>> g(n);
        for(int i = 1; i < n; i ++) g[p[i]].pb(i);
        auto disv = distance(v);
        auto disg = distance(g);
        int dv = *max_element(all(disv));
        int ig = -1, dg = -1;
        rep(i, n) if(dg < disg[i]) {
            dg = disg[i];
            ig = i;
        }
        if(dg < dv) return -1;
        rep(_, dg - dv) ig = p[ig];
        auto ghash = tohash(g);
        int x = ghash[ig];
        int cnt = 0;
        auto dfs = [&](auto dfs, int now) -> int {
            vector<int> ret;
            foa(e, v[now]) {
                cnt ++;
                ret.pb(dfs(dfs, e));
            }
            foa(e, inv[x]) {
                cnt ++;
                ret.pb(e);
            }
            if(cnt > 1000000) return -1;
            sort(all(ret));
            if((int)ret.size() and ret[0] == -1) return -1;
            if(!mp.count(ret)) {
                inv.push_back(ret);
                mp[ret] = id ++;
            }
            return mp[ret];
        };
        int r1 = dfs(dfs, 0);
        if(r1 == -1) return -1;
        multiset<int> st;
        foa(e, inv[hs]) st.insert(e);
        foa(e, inv[r1]) {
            if(st.find(e) != st.end()) st.erase(st.find(e));
            else return -1;
        }
        if(st.empty()) return x;
        return -1;
    };
    
    auto test = [&](vector<vector<int>> &v1, vector<vector<int>> &v2) -> pair<int, int> {
        auto dis1 = distance(v1);
        int d1 = *max_element(all(dis1));
        if(dc < d1) return {-1, -1};
        int i = idx;
        rep(_, dc - d1) i = pc[i];
        int x = Chash[i];
        int cnt = 0;
        auto dfs = [&](auto dfs, int now) -> int {
            vector<int> ret;
            foa(e, v1[now]) {
                cnt ++;
                ret.pb(dfs(dfs, e));
            }
            foa(e, inv[x]) {
                cnt ++;
                ret.pb(e);
            }
            if(cnt > 1000000) return -1;
            sort(all(ret));
            if((int)ret.size() and ret[0] == -1) return -1;
            if(!mp.count(ret)) {
                inv.push_back(ret);
                mp[ret] = id ++;
            }
            return mp[ret];
        };
        int r1 = dfs(dfs, 0);
        if(r1 == -1) return {-1, -1};
        multiset<int> st;
        foa(e, inv[Chash[0]]) st.insert(e);
        foa(e, inv[r1]) {
            if(st.find(e) != st.end()) st.erase(st.find(e));
            else return {-1, -1};
        }
        vector<int> vec;
        foa(e, st) vec.pb(e);
        if(!mp.count(vec)) {
            inv.push_back(vec);
            mp[vec] = id ++;
        } 
        auto y = test2(v2, mp[vec]);
        if(y == -1) x = -1;
        return {x, y};
        
    };
    
    {
        auto [x, y] = test(va, vb); // hash, hash
        if(x != -1) {
            auto px = i2p(x);
            auto py = i2p(y);
            cout << px.size() << " " << py.size() << endl;
            foa(e, px) cout << e << " ";
            cout << endl;
            foa(e, py) cout << e << " ";
            cout << endl;
            return;
        }
    }{
        auto [y, x] = test(vb, va);
        if(x != -1) {
            auto px = i2p(x);
            auto py = i2p(y);
            cout << px.size() << " " << py.size() << endl;
            foa(e, px) cout << e << " ";
            cout << endl;
            foa(e, py) cout << e << " ";
            cout << endl;
            return;
        }
    }

    cout << "Impossible" << endl;
}
int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int t;
    cin >> t;
    while(t --) solve();
    return 0;
}
Source code, Language: C++20

这程序好像有点Bug，我给组数据试试？

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3524kb

input:

2
2 3 10
0 1
0 1 2
0 1 1 3 4 3 6 3 1 9
4 3 10
0 1 2 2
0 1 2
0 1 1 3 4 3 6 3 1 9

output:

Impossible
2 1
0 1 
0

result:

ok 2 cases passed

Test #2:

score: 0
Accepted
time: 411ms
memory: 14988kb

input:

11122
3 3 11
0 1 1
0 1 1
0 1 1 1 4 4 1 1 8 8 1
7 2 10
0 1 2 2 2 1 1
0 1
0 1 2 1 1 5 5 5 1 1
7 8 14
0 1 2 1 1 1 1
0 1 2 1 1 1 1 1
0 1 1 3 1 1 1 1 1 1 1 11 1 1
4 8 11
0 1 1 1
0 1 1 1 1 1 6 6
0 1 1 1 1 1 6 6 1 1 1
3 4 13
0 1 1
0 1 1 1
0 1 1 3 1 5 1 1 8 1 10 1 12
11 2 14
0 1 2 1 4 4 4 1 1 1 1
0 1
0 1 1 ...

output:

3 1
0 1 1 
0 
1 2
0 
0 1 
1 1
0 
0 
1 1
0 
0 
2 2
0 1 
0 1 
1 2
0 
0 1 
1 5
0 
0 1 1 1 4 
1 1
0 
0 
8 2
0 1 1 1 1 5 5 5 
0 1 
1 1
0 
0 
4 1
0 1 1 1 
0 
3 1
0 1 1 
0 
5 1
0 1 1 1 4 
0 
1 1
0 
0 
1 1
0 
0 
1 1
0 
0 
1 1
0 
0 
2 1
0 1 
0 
5 1
0 1 1 1 1 
0 
1 1
0 
0 
1 3
0 
0 1 1 
1 2
0 
0 1 
3 1
0 1 1 ...

result:

ok 11122 cases passed

Test #3:

score: 0
Accepted
time: 1ms
memory: 3644kb

input:

1
5 5 49
0 1 1 3 1
0 1 2 1 2
0 1 2 3 4 1 6 7 8 9 1 11 12 13 14 11 16 17 18 19 1 21 22 23 24 1 26 26 1 1 30 31 31 30 30 35 36 36 35 30 40 41 41 40 1 45 46 46 45

output:

5 5
0 1 2 3 4 
0 1 1 3 3

result:

ok 1 cases passed

Extra Test:

score: 0
Extra Test Passed
English 繁體中文 简体中文

Server Time: 2025-02-08 16:42:23 | OpenSource Project