Submission #1210389

#	Time	Username	Problem	Language	Result	Execution time	Memory
1210389		tosivanmak	Simurgh (IOI17_simurgh)	C++20	100 / 100	86 ms	21716 KiB

simurgh

#include<bits/stdc++.h>
#include "simurgh.h"
using namespace std;
#define ll long long

// static int MAXQ = 30000;

// static int n, m, q = 0;
// static vector<int> u, v;
// static vector<bool> goal;

// static void wrong_answer() {
//     cout<<"No\n";
// 	exit(0);
// }
// static bool is_valid(const vector<int>& r) {
// 	if(int(r.size()) != n - 1)
// 		return false;

// 	for(int i = 0; i < n - 1; i++)
// 		if (r[i] < 0 || r[i] >= m)
// 			return false;

// 	return true;
// }

// static int _count_common_roads_internal(const vector<int>& r) {
// 	if(!is_valid(r)){
// 		wrong_answer();
//     }
// 	int common = 0;
// 	for(int i = 0; i < n - 1; i++) {
// 		bool is_common = goal[r[i]];
// 		if (is_common)
// 			common++;
// 	}
// 	return common;	
// }

// int count_common_roads(const vector<int>& r) {
// 	q++;
// 	if(q > MAXQ)
// 		wrong_answer();

// 	return _count_common_roads_internal(r);
// }
vector<ll>adj[505];
struct Edge{
    ll u,v,id;
};

// int count_common_roads(int[] r)

struct DSU{
    vector<ll>fa,siz;
    void init(ll n){
        fa.resize(n+5); siz.resize(n+5);
        for(int i=0;i<n+5;i++){
            fa[i]=i,siz[i]=1;
        }
    }
    ll root(ll x){
        if(fa[x]==x)return x;
        return fa[x]=root(fa[x]);
    }
    void unite(ll u, ll v){
        u=root(u); v=root(v);
        if(siz[u]<siz[v])swap(u,v);
        fa[v]=u; siz[u]+=siz[v];
    }
};
int Query(vector<int>r){
    // cout<<"Lag "<<r.size()<<endl;
    int val=count_common_roads(r);
    return val;
}
enum Type {Normal, Royal, Undefined};
struct Graph{
    vector<Edge>edge,tedge;
    vector<vector<pair<ll,ll> > >adj,tadj;
    vector<vector<ll> >res;
    vector<ll>dep,fa,highest,eid;
    vector<bool>vis;
    vector<Type>type;
    vector<ll>tree; int tree_val;
    void init(ll n){
        adj.resize(n+5); tadj.resize(n+5); vis.resize(n+5); dep.resize(n+5); fa.resize(n+5); type.resize(n*n+5); highest.resize(n+5); eid.resize(n+5); res.resize(n+5);
        for(int i=0;i<n+5;i++){
            res[i].resize(n+5);
        }
        for(int i=0;i<n+5;i++){
            highest[i]=-1; eid[i]=-1;
        }
        for(int i=0;i<n*n+5;i++){
            type[i]=Type::Undefined;
        }
    }
    void add_edge(ll u, ll v, ll id){
        edge.push_back({u,v,id}); adj[u].push_back({v,id}); adj[v].push_back({u,id});
        res[u][v]=res[v][u]=id;
    }
    void dfs(ll s){
        vis[s]=1;
        for(auto& [u,id]: adj[s]){
            if(!vis[u]){
                dep[u]=dep[s]+1;
                dfs(u); tadj[s].push_back({u,id}); tadj[u].push_back({s,id});
                fa[u]=s; tedge.push_back({s,u,id});
                tree.push_back(id);
            }
        }
    }
    void construct(ll s){
        vis[s]=1;
        highest[s]=dep[s]; eid[s]=-1;
        for(auto& [u,id]: adj[s]){
            if(!vis[u]){
                construct(u);
                if(highest[u]<highest[s]){
                    highest[s]=highest[u]; eid[s]=eid[u];
                }
            }
            else{
                if(u==fa[s])continue;
                if(dep[u]<highest[s]){
                    highest[s]=dep[u]; eid[s]=id;
                }
            }
        }
    }
    void clear(ll n){
        for(int i=0;i<=n;i++)vis[i]=0;
    }
    void build_induced_subtree(ll n){
        dep[0]=1;
        dfs(0); clear(n);
        construct(0); clear(n);
        // cout<<"Constructed\n";
        // for(int i=0;i<tree.size();i++){
        //     cout<<tree[i]<<" ";
        // }
        // cout<<'\n';
    }
    vector<ll>edge_list;
    int pull(ll x, int add){
        vector<int>qrylist;
        if(x==-1){
            for(auto& u: tree){
                qrylist.push_back(u);
            }
            return Query(qrylist);
        }
        else{
            qrylist.push_back(add);
            for(auto& u: tree){
                if(u!=x){
                    qrylist.push_back(u);
                }
            }
            // cout<<qrylist.size()<<'\n';
            // for(auto& u: qrylist){
            //     cout<<u<<" ";
            // }
            return Query(qrylist);
        }
    }
    void build(ll u, ll v){
        while(dep[u]!=dep[v]){
            edge_list.push_back(res[u][fa[u]]); u=fa[u];
        }
    }
    void process(ll edge_id){
        vector<pair<ll,ll> >alls;
        ll cnt=0;
        ll wrt;
        for(auto& u: edge_list){
            if(type[u]!=Type::Undefined){
                cnt++; 
                if(cnt==1){
                    wrt=pull(u,edge_id);
                    if(type[u]==Type::Royal){
                        if(tree_val==wrt)type[edge_id]=Type::Royal;
                        else type[edge_id]=Type::Normal;
                    }
                    else{
                        if(tree_val==wrt)type[edge_id]=Type::Normal;
                        else type[edge_id]=Type::Royal;
                    }
                }
                continue;
            }
            alls.push_back({pull(u,edge_id),u});
        }
        sort(alls.begin(),alls.end());
        // add 1, neutral, minus 1
        if(type[edge_id]==Type::Undefined){
            if(alls[0].first==alls[alls.size()-1].first){
                if(tree_val==alls[0].first){
                    for(int i=0;i<alls.size();i++){
                        type[alls[i].second]=Type::Normal;
                    }
                    type[edge_id]=Type::Normal;
                }
                else{
                    for(int i=0;i<alls.size();i++){
                        type[alls[i].second]=Type::Royal;
                    }
                    type[edge_id]=Type::Normal;
                }
            }
            else{
                ll mini=alls[0].first; ll maxi=alls[alls.size()-1].first;
                if(mini<tree_val){
                    type[edge_id]=Type::Normal;
                    for(int i=0;i<alls.size();i++){
                        if(alls[i].first<tree_val)type[alls[i].second]=Type::Royal;
                        else type[alls[i].second]=Type::Normal;
                    }
                }
                else{
                    type[edge_id]=Type::Royal;
                    for(int i=0;i<alls.size();i++){
                        if(alls[i].first==tree_val)type[alls[i].second]=Type::Royal;
                        else type[alls[i].second]=Type::Normal;
                    }
                }
            }
        }
        else{
            for(int i=0;i<alls.size();i++){
                if(alls[i].first==tree_val){
                    type[alls[i].second]=type[edge_id];
                }
                else{
                    if(type[edge_id]==Type::Royal)type[alls[i].second]=Type::Normal;
                    else type[alls[i].second]=Type::Royal;
                }
            }
        }
        edge_list.clear();
    }
    void find_tree_edge(ll n){
        tree_val=pull(-1,-1);
        for(int i=1;i<n;i++){
            ll req=res[i][fa[i]];
            if(type[req]!=Type::Undefined)continue;
            if(highest[i]!=dep[i]){
                auto [u,v,id]=edge[eid[i]];
                // cout<<"Debug : "<<i<<" "<<u<<" "<<v<<" "<<eid[i]<<'\n';
                if(dep[u]<dep[v]){
                    swap(u,v);
                }
                build(u,v); process(id);
            }
            else{
                ll req=res[i][fa[i]];
                type[req]=Type::Royal;
            }
        }
    }
    ll qry(ll n, vector<Edge>& lst, ll l, ll r){
        DSU d; d.init(n);
        ll royals=0; // tedge
        vector<int>used;
        for(int i=l;i<=r;i++){
            auto& [u,v,id]=lst[i];
            d.unite(u,v); used.push_back(id);
        }
        for(auto& [u,v,id]: tedge){
            if(d.root(u)!=d.root(v)){
                used.push_back(id);
                d.unite(u,v); royals+=(type[id]==Type::Royal);
            }
        }
        // cout<<used.size()<<endl;
        // for(int i=0;i<(int)used.size();i++){
        //     cout<<used[i]<<' ';
        // }
        return Query(used)-royals;
    }
    void dc(ll n, ll l, ll r, ll rem, vector<Edge>& lst){
        if(l==r){
            type[lst[l].id]=Type::Royal; return;
        }
        ll mid=(l+r)>>1;
        ll lrem=qry(n,lst,l,mid); ll rrem=rem-lrem;
        if(lrem!=0){
            dc(n,l,mid,lrem,lst);
        }
        if(rrem!=0){
            dc(n,mid+1,r,rrem,lst);
        }
    }
    void deal(vector<Edge>lst, ll n){
        DSU d;
        d.init(n);
        ll royals=0; // tedge
        vector<int>used;
        for(auto& [u,v,id]: lst){
            d.unite(u,v); used.push_back(id);
        }
        for(auto& [u,v,id]: tedge){
            if(d.root(u)!=d.root(v)){
                used.push_back(id);
                d.unite(u,v); royals+=(type[id]==Type::Royal);
            }
        }
        // cout<<used.size()<<endl;
        // for(int i=0;i<used.size();i++){
        //     cout<<used[i]<<' ';
        // }
        ll val=Query(used);
        if(val==royals){
            for(int i=0;i<(int)lst.size();i++){
                type[lst[i].id]=Type::Normal;
            }
            return;
        }
        else{
            dc(n,0,(int)lst.size()-1,val-royals,lst);
            for(int i=0;i<(int)lst.size();i++){
                if(type[lst[i].id]==Type::Undefined){
                    type[lst[i].id]=Type::Normal;
                }
            }
            return;
        }
    }
    void remaining(ll n){
        DSU dd[n+5]; vector<Edge>lst[n+5];
        for(int i=1;i<=n;i++)dd[i].init(n);
        for(auto& [u,v,id]: edge){
            if(type[id]==Type::Undefined){
                ll l=1,r=n;
                while(l<r){
                    ll mid=(l+r)>>1;
                    if(dd[mid].root(u)!=dd[mid].root(v))r=mid;
                    else l=mid+1;
                }
                lst[l].push_back({u,v,id}); dd[l].unite(u,v);
            }
        }
        for(int i=1;i<=n;i++){
            if(lst[i].size()){
                deal(lst[i],n);
            }
        }
    }
};
vector<int>find_roads(int n, vector<int>u, vector<int>v){
    int m=u.size();
    for(int i=0;i<m;i++){
        adj[u[i]].push_back(v[i]); adj[v[i]].push_back(u[i]);
    }
    Graph g;
    g.init(n);
    for(int i=0;i<m;i++){
        g.add_edge(u[i],v[i],i);
    }
    g.build_induced_subtree(n);
    // cout<<"Check\n";
    g.find_tree_edge(n);
    // cout<<"Check\n";
    // for(int i=0;i<(int)u.size();i++){
    //     cout<<g.type[i]<<'\n';
    // }
    // cout<<'\n';
    g.remaining(n);
    vector<int>ans;
    for(int i=0;i<(int)u.size();i++){
        if(g.type[i]==Type::Royal){
            // cout<<g.type[i]<<'\n';
            ans.push_back(i);
        }
    }
    // cout<<ans.size()<<"\n";
    // for(auto& u: ans){
    //     cout<<u<<"\n";
    // }
    return ans;
}
// int main() {
// 	assert(2 == scanf("%d %d", &n, &m));

// 	u.resize(m);
// 	v.resize(m);

// 	for(int i = 0; i < m; i++)
// 		assert(2 == scanf("%d %d", &u[i], &v[i]));

// 	goal.resize(m, false);

// 	for(int i = 0; i < n - 1; i++) {
// 		int id;
// 		assert(1 == scanf("%d", &id));
// 		goal[id] = true;
// 	}
    
// 	vector<int> res = find_roads(n, u, v);
// 	if(_count_common_roads_internal(res) != n - 1)
// 		wrong_answer();

//     cout<<"Yes\n";

// 	return 0;
// }

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