Submission #1016145

#	Time	Username	Problem	Language	Result	Execution time	Memory
1016145		hotboy2703	Simurgh (IOI17_simurgh)	C++17	100 / 100	104 ms	6740 KiB

simurgh

#include "simurgh.h"

#include<bits/stdc++.h>
using namespace std;
using ll = int;
#define pll pair <ll,ll>
#define fi first
#define se second
#define MP make_pair
#define sz(a) (ll((a).size()))
#define BIT(mask,i) (((mask) >> (i))&1)
#define MASK(i) (1LL << (i))
namespace TRUNG{
    const ll MAXN = 510;
    ll n,m;
    ll ans[MAXN*MAXN];
    vector <pll> g[MAXN];
    bool sus[MAXN*MAXN];
    ll in[MAXN],out[MAXN];
    ll timeDFS;
    vector <pll> a;
    ll cnt_query;
    void dfs(ll u,ll p){
        in[u] = ++timeDFS;
        for (auto tmp:g[u]){
            ll v = tmp.fi,id = tmp.se;
            if (v==p)continue;
            dfs(v,u);
        }
        out[u] = timeDFS;
    }
    bool sus_edge(ll i,ll j){
        ll x = a[i].fi;
        if (in[a[i].se] > in[x])x = a[i].se;
//        cout<<i<<' '<<j<<' '<<x<<endl;
        if ((in[x] <= in[a[j].fi] && in[a[j].fi] <= out[x])+(in[x] <= in[a[j].se] && in[a[j].se] <= out[x])==1)return 1;
        return 0;
    }

    namespace DSU{
        ll dsu[MAXN];
        void init(){
            memset(dsu,-1,sizeof dsu);
        }
        ll f(ll x){
            if (dsu[x] < 0)return x;
            return (dsu[x] = f(dsu[x]));
        }
        void join(ll x,ll y){
            x = f(x),y = f(y);
            if (x!=y){
                if (dsu[x] > dsu[y])swap(x,y);
                dsu[x] += dsu[y];
                dsu[y] = x;
            }
        }
    }
    bitset <MAXN> bs[MAXN];
    ll ind[MAXN][MAXN];
    vector <ll> tree,extra;
    ll superior_count(vector <ll> all){
        DSU::init();
        for (auto x:all){
            DSU::join(a[x].fi,a[x].se);
        }
        ll res = 0;
        for (auto x:tree){
            if (DSU::f(a[x].fi) != DSU::f(a[x].se)){
                DSU::join(a[x].fi,a[x].se);
                all.push_back(x);
                res-=ans[x];
            }
        }
        assert(++cnt_query<=8000);
        res += count_common_roads(all);
        return res;
    }
    void solve(vector <ll> all,ll k){
        if (k==0)return;
        if (sz(all) == 1){
            ans[all[0]] = k;
            return;
        }
        ll mid = sz(all) / 2;
        vector <ll> L,R;
        for (ll i = 0;i < sz(all);i ++){
            if (i < mid)L.push_back(all[i]);
            else R.push_back(all[i]);
        }
        ll cnt_L = superior_count(L);
        solve(L,cnt_L);
        solve(R,k-cnt_L);
    }
}
std::vector<int> find_roads(int N, std::vector<int> U, std::vector<int> V) {
    using namespace TRUNG;
    memset(ans,-1,sizeof ans);
    ll m = sz(U),n=N ;
    a.resize(m);
    for (ll i = 0;i < m;i ++)a[i] = MP(U[i],V[i]);
    DSU::init();
    for (ll i = 0;i < m;i ++){
        if (DSU::f(a[i].fi) != DSU::f(a[i].se)){sus[i] = 1;tree.push_back(i);}
        DSU::join(a[i].fi,a[i].se);
    }
    DSU::init();
    for (ll i = 0;i < m;i ++){
        if (sus[i])continue;
        if (DSU::f(a[i].fi) != DSU::f(a[i].se))extra.push_back(i);
        DSU::join(a[i].fi,a[i].se);
    }
    for (auto id:tree){
        g[a[id].fi].push_back(MP(a[id].se,id));
        g[a[id].se].push_back(MP(a[id].fi,id));
    }
    dfs(0,0);
//    cout<<in[4]<<' '<<out[4]<<' '<<in[1]<<' '<<out[1]<<endl;
//    for (auto x:tree)cout<<x<<' ';
//    cout<<'\n';
//    for (auto x:extra)cout<<x<<' ';
//    cout<<'\n';
//    cout<<sus_edge(4,7)<<endl;

    ll cur = count_common_roads(tree);
        assert(++cnt_query<=8000);

    for (auto id:tree){
//        cout<<id<<endl;
        if (ans[id] != -1)continue;
        for (auto x:extra){
            if (sus_edge(id,x)){
//                cout<<"WOW "<<x<<' '<<id<<endl;
                auto cal = [&](ll y){
                    vector <ll> tmp;
                    for (auto sss:tree)if (sss != y)tmp.push_back(sss);
                    tmp.push_back(x);
                            assert(++cnt_query<=8000);
//                    cout<<"CAL "<<y<<": ";
//                    for (auto z:tmp)cout<<z<<' ';
//                    cout<<endl;
                    ll res = count_common_roads(tmp);
//                    cout<<"VAL "<<res<<endl;
                    return res;
                };
                vector <ll> cycle;
                for (auto y:tree){
                    if (sus_edge(y,x)){
                        cycle.push_back(y);
                    }
                }
//                for (auto y:cycle)cout<<y<<' ';
//                cout<<endl;
                ll sum = -1;
                if (ans[x] != -1)sum = ans[x] + cur;
                for (auto y:cycle){
                    if (ans[y] != -1 && sum == -1){
                        sum = cal(y) + ans[y];
                        break;
                    }
                }
                if (sum==-1){
                    vector <ll> com(sz(cycle));
                    for (ll j = 0;j < sz(cycle);j ++){
                        com[j] = cal(cycle[j]);
                        if (com[j] < cur)sum = cur;
                        if (com[j] > cur)sum = cur+1;
//                        cout<<cycle[j]<<' '<<com[j]<<endl;
                    }
                    if (sum == -1)sum = cur;
                    for (ll j = 0;j < sz(cycle);j ++){
                        ans[cycle[j]] = sum - com[j];
                    }
                    ans[x] = sum - cur;
                }
                else{
                    for (auto y:cycle)if (ans[y] == -1){
                        ans[y] = sum - cal(y);
                    }
                    ans[x] = sum - cur;
                }
                break;
            }
        }
        if (ans[id] == -1)ans[id] = 1;
    }
//    for (ll j = 0;j < m;j ++)cout<<ans[j]<<' ';
//    cout<<endl;
    for (ll j = 0;j < m;j ++){
        pll x = a[j];
        ind[x.fi][x.se]=ind[x.se][x.fi]=j;
        if (ans[j] == -1)bs[x.fi][x.se] = bs[x.se][x.fi] = 1;
    }
    while (true){
        bitset <MAXN> rem;
        rem.set();
        bitset <MAXN> tmp;
        vector <ll> cur;
        for (ll i = 0;i < n;i ++){
            if (rem[i]){
                queue <ll> q;
                q.push(i);
                rem[i] = 0;
                while (!q.empty()){
                    ll u = q.front();
                    q.pop();
                    tmp = rem & bs[u];
                    for (ll v = tmp._Find_first();v < n;v = tmp._Find_next(v)){
                        cur.push_back(ind[u][v]);
                        bs[u][v] = bs[v][u] = 0;
                        q.push(v);
                        rem[v] = 0;
                    }
                }
            }
        }
        if (!sz(cur))break;
//        cout<<sz(cur)<<' '<<cur[0]<<endl;
        solve(cur,superior_count(cur));
    }
    vector <ll> r;
    for (ll i = 0;i < m;i ++)if (ans[i]==1)r.push_back(i);
//    assert(cnt_query<=8000);
//    count_common_roads
    return r;
}

Compilation message (stderr)

simurgh.cpp: In function 'void TRUNG::dfs(ll, ll)':
simurgh.cpp:26:27: warning: unused variable 'id' [-Wunused-variable]
   26 |             ll v = tmp.fi,id = tmp.se;
      |                           ^~

• Subtask 1: 13 / 13
• Subtask 2: 17 / 17
• Subtask 3: 21 / 21
• Subtask 4: 19 / 19
• Subtask 5: 30 / 30