Submission #566443

#	Time	Username	Problem	Language	Result	Execution time	Memory
566443		BJoozz	Alternating Current (BOI18_alternating)	C++14	100 / 100	106 ms	16112 KiB

alternating

#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define X first
#define Y second
#define int long long
void maxx(int &a,int b){if(b>a) a=b;}
void minn(int &a,int b){if(b<a) a=b;}
mt19937 rng(time(0));
int randint(int l,int r){
    return uniform_int_distribution < int > (l,r) (rng);
}
using ll = long long;
using ii = pair < int , int >;
const int MAX=1e5+3,inf=1e9,mod=1e9+7;
using ld = long double;
int n,m;
vector < int > pr[MAX];
int C[MAX];
bool vs[MAX];
bool in[MAX],ok[MAX];
bool good[MAX];
int L[MAX],R[MAX];
ii trace[MAX];
bool res[MAX];
int dis(int u,int v){
    return (v+n-u)%n+1;
}
bool cmp(int u,int v,int z){
    return dis(u,v)+dis(v,z)-1==dis(u,z);
}
signed main(){
    //freopen("Alternating Current.inp","r",stdin);freopen("Alternating Current.out","w",stdout);
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin>>n>>m;
    int U=1,V=1;
    map < ii , int > mp;
    for(int i=1,x,y;i<=m;i++){
        cin>>x>>y;
        mp[ii(x,y)]=i;
        pr[x].pb(y);
        if(dis(U,V)<dis(x,y)){
            U=x;V=y;
        }
        if(x<=y){
            C[x]++;C[y+1]--;
        }else{
            C[x]++;C[1]++;C[y+1]--;
        }
    }
    for(int i=1;i<=n;i++)
    {
        C[i]+=C[i-1];
        if(C[i]<2){
            cout<<"impossible";return 0;
        }
        if(C[i]>2) ok[i]=1;
    }
    for(int i=1;i<=n;i++) L[i]=i-1,R[i]=i+1;

    L[1]=n;R[n]=1;
    vector < ii > vec;
    queue < int > Q;

    if(R[V]==U){
            res[mp[ii(U,V)]]=1;
        for(int i=1;i<=m;i++) cout<<res[i];//cout<<'\n';
        //getans(vec);
        return 0;
    }
    bool las=1;
    for(int i=U;i!=R[V];i=R[i]){
        in[i]=1;
        good[i]=las;
        las&=ok[i];
    }
    //for(int i=1;i<=n;i++)cout<<C[i]<<' ';cout<<'\n';

    int dich=-1;
    //cout<<U<<' '<<V<<'\n';
    Q.push(R[V]);vs[R[V]]=1;trace[R[V]]=ii(U,V);
    ii pd;
    while(!Q.empty() && dich==-1){
        int p = Q.front();Q.pop();
        //cout<<p<<'\n';
        for(int u:pr[p]){
            u=R[u];
            //cout<<p<<' '<<u<<'\n';
            if(in[u]){
                if(!in[p] &&good[u]){
                    pd=ii(p,L[u]);
                    dich=p;break;
                }
                if(in[p] && good[u] && cmp(U,u,p)){
                    pd=ii(p,L[u]);
                    dich=p;break;
                }
                continue;
            }
            if(!vs[u]){
                vs[u]=1;trace[u]=ii(p,L[u]);
                Q.push(u);
            }
        }
        //cout<<L[p]<<' '<<ok[7]<<' '<<vs[7]<<'\n';
        //cout<<trace[p].X<<'\n';
        if(ok[L[p]] && !vs[L[p]] && L[p]!=trace[p].X){
            vs[L[p]]=1;
            trace[L[p]]=trace[p];
            Q.push(L[p]);
        }
    }
    //cout<<dich<<'\n';
    if(dich==-1){
        cout<<"impossible";return 0;
    }
    int numQ=m;
    //cout<<pd.X<<' '<<pd.Y<<'\n';
    res[mp[pd]]=1;
    while(numQ--){
        ii now=trace[dich];
        //cout<<now.X<<' '<<now.Y<<'\n';
        res[mp[now]]=1;
        dich=now.X;
        if(now==ii(U,V)) break;
    }
    /// U pd.Y dich
    if(pd.Y==L[U] || dich==R[V] ||
       dis(U,pd.Y)+dis(dich,V)<=dis(U,V)){

    }else{
        //res[mp[ii(U,V)]]=0;
    }
    for(int i=1;i<=m;i++) cout<<res[i];//cout<<'\n';
}

• Subtask 1: 13 / 13
• Subtask 2: 20 / 20
• Subtask 3: 22 / 22
• Subtask 4: 19 / 19
• Subtask 5: 26 / 26