Submission #925724

#	Time	Username	Problem	Language	Result	Execution time	Memory
925724		HuyQuang_re_Zero	Simurgh (IOI17_simurgh)	C++14	100 / 100	161 ms	9060 KiB

simurgh

#include <bits/stdc++.h>
#define ll long long
#define db long double
#define N 505
#define II pair <ll,ll>
#define III pair <ll,II>
#define IV pair <vector <int>,vector <int> >
#define IDB pair <db,int>
#define TII pair <treap*,treap*>
#define fst first
#define snd second
#define BIT(x,i) ((x>>i)&1)
#define pi acos(-1)
#define to_radian(x) (x*pi/180.0)
#define to_degree(x) (x*180.0/pi)
#define Log(x) (31-__builtin_clz((int)x))
#define LogLL(x) (63-__builtin_clzll((ll)x)
using namespace std;
#include "simurgh.h"
//#define count_common_roads(vec) IR.common(vec)
struct Interactive
{
    int n;
    set <int> s;
    void Init(int _n)
    {
        n=_n;
        int x;
        for(int i=1;i<n;i++) cin>>x,s.insert(x);
    }
    int common(vector <int> vec)
    {
        int res=0;
        for(int x:vec)
            if(s.find(x)!=s.end()) res++;
        return res;
    }
} IR;
struct DSU
{
    int r[N];
    void Init(int n)
    {
        for(int u=1;u<=n;u++) r[u]=u;
    }
    int root(int u) { return (u==r[u]) ? u : r[u]=root(r[u]); }
    bool join(int u,int v)
    {
        if(root(u)==root(v)) return 0;
        r[root(u)]=root(v);
        return 1;
    }
} DS;




int n,m,i,j,u,v,in_MyTree[N*N],in_ZalTree[N*N],num[N][N],p[N],done[N],U[N*N],V[N*N],MyTree_score,h[N],deg[N];
vector <int> MyTree,a[N];
int Score(vector <int> vec)
{
    DS.Init(n);
    vector <int> NowTree;
    for(int x:vec)
    {
        DS.join(U[x],V[x]);
        NowTree.push_back(x);
    }
    int added_score=0;
    for(int x:MyTree)
        if(DS.join(U[x],V[x]))
        {
            NowTree.push_back(x);
            added_score+=in_ZalTree[x];
        }
    return count_common_roads(NowTree)-added_score;
}
vector <int> MyTree_Replace(int u,int v)
{
    vector <int> res;
    for(int x:MyTree)
        if(x!=u) res.push_back(x);
    res.push_back(v);
    return res;
}
void DFS(int u)
{
    for(int v:a[u])
        if(p[v]==0)
        {
            p[v]=u; h[v]=h[u]+1;
            DFS(v);
            MyTree.push_back(num[u][v]);
            in_MyTree[num[u][v]]=1;
        }
}
vector <int> find_roads(int _n,vector <int> _U,vector <int> _V)
{
    n=_n; m=_U.size();
    for(i=0;i<m;i++) U[i]=_U[i]+1,V[i]=_V[i]+1;
    for(i=0;i<m;i++)
    {
        u=U[i]; v=V[i];
        a[u].push_back(v); a[v].push_back(u);
        num[u][v]=num[v][u]=i;
    }
    /////////////////////////////////////////////////////////////////////////////////////////////////////////////////
    //Determine MyTree
    p[1]=-1;
    DFS(1);
    MyTree_score=count_common_roads(MyTree);
    memset(in_ZalTree,-1,sizeof(in_ZalTree));
    for(i=0;i<m;i++)
        if(!in_MyTree[i])
        {
            vector <int> path;
            auto Walk=[&](int u,int v)
            {
                int res=-1;
                if(h[u]<h[v]) swap(u,v);
                while(h[u]>h[v])
                {
                    if(in_ZalTree[num[u][p[u]]]==-1)
                        path.push_back(num[u][p[u]]);
                    else res=num[u][p[u]];
                    u=p[u];
                }
                while(u!=v)
                {
                    if(in_ZalTree[num[u][p[u]]]==-1)
                        path.push_back(num[u][p[u]]);
                    else res=num[u][p[u]];
                    u=p[u];
                    if(in_ZalTree[num[v][p[v]]]==-1)
                        path.push_back(num[v][p[v]]);
                    else res=num[v][p[v]];
                    v=p[v];
                }
                return res;
            };
            int determined_edge=Walk(U[i],V[i]);
            if(path.size()==0) continue;
            if(determined_edge==-1)
            {
                vector <int> Bigger,Smaller,Equal;
                for(int x:path)
                {
                    int k=count_common_roads(MyTree_Replace(x,i));
                    if(MyTree_score>k)
                        Bigger.push_back(x);
                    else if(MyTree_score<k)
                        Smaller.push_back(x);
                    else Equal.push_back(x);
                }
                if(Bigger.size()>0)
                {
                    for(int x:Bigger) in_ZalTree[x]=1;
                    for(int x:Equal) in_ZalTree[x]=0;
                }
                else if(Smaller.size()>0)
                {
                    for(int x:Smaller) in_ZalTree[x]=0;
                    for(int x:Equal) in_ZalTree[x]=1;
                }
                else
                    for(int x:Equal) in_ZalTree[x]=0;
            }
            else
            {
                int k=count_common_roads(MyTree_Replace(determined_edge,i));
                int i_score=in_ZalTree[determined_edge];
                if(k>MyTree_score) i_score++;
                if(k<MyTree_score) i_score--;

                for(int x:path)
                {
                    int k=count_common_roads(MyTree_Replace(x,i));
                    in_ZalTree[x]=i_score;
                    if(MyTree_score>k) in_ZalTree[x]++;
                    if(MyTree_score<k) in_ZalTree[x]--;
                }
            }
        }
    for(int x:MyTree)
        if(in_ZalTree[x]==-1) in_ZalTree[x]=1;


    //////////////////////////////////////////////////////////////////////////////////////////////////
    //Determine ZalTree
    queue <int> q;
    for(u=1;u<=n;u++)
    {
        vector <int> vec;
        for(int v:a[u]) vec.push_back(num[u][v]);
        deg[u]=Score(vec);
        if(deg[u]==1) q.push(u);
    }


    vector <int> res;
    for(i=1;i<n;i++)
    {
        int u=q.front(); q.pop();
        done[u]=1;
        vector <int> candidate;
        for(int v:a[u])
            if(done[v]==0)
                candidate.push_back(num[u][v]);
        int l=0,r=candidate.size()-1;
        while(l<r)
        {
            int mid=(l+r)>>1;
            vector <int> vec;
            for(j=0;j<=mid;j++) vec.push_back(candidate[j]);
            if(Score(vec)>0) r=mid; else l=mid+1;
        }
        int x=candidate[l];
        res.push_back(x);
        if(U[x]==u) v=V[x]; else v=U[x];
        deg[v]--;
        if(deg[v]==1) q.push(v);
    }
    return res;
}
/*
int main()
{
    freopen("simurgh.inp","r",stdin);
    freopen("simurgh.out","w",stdout);
    int n,k,u,v;
    cin>>n;
    IR.Init(n);
    vector <int> U,V;
    while(cin>>u>>v) U.push_back(u),V.push_back(v);
    vector <int> vec=find_roads(n,U,V);
    for(int x:vec) cout<<x<<" ";
}
*/

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