oj.uz

Submission #566439

# Submission time Handle Problem Language Result Execution time Memory
566439 2022-05-22T10:09:24 Z BJoozz Alternating Current (BOI18_alternating) C++14
0 / 100
 144 ms 16020 KB 
#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
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 2688 KB Output is correct
2 Correct 2 ms 2644 KB Output is correct
3 Correct 2 ms 2644 KB Output is correct
4 Correct 8 ms 2652 KB Output is correct
5 Incorrect 2 ms 2644 KB no wires in direction 1 between segments 1 and 2
6 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 2688 KB Output is correct
2 Correct 2 ms 2644 KB Output is correct
3 Correct 2 ms 2644 KB Output is correct
4 Correct 8 ms 2652 KB Output is correct
5 Incorrect 2 ms 2644 KB no wires in direction 1 between segments 1 and 2
6 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 2688 KB Output is correct
2 Correct 2 ms 2644 KB Output is correct
3 Correct 2 ms 2644 KB Output is correct
4 Correct 8 ms 2652 KB Output is correct
5 Incorrect 2 ms 2644 KB no wires in direction 1 between segments 1 and 2
6 Halted 0 ms 0 KB -

Subtask #4
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 6984 KB Output is correct
2 Correct 4 ms 4948 KB Output is correct
3 Correct 27 ms 8680 KB Output is correct
4 Correct 27 ms 10324 KB Output is correct
5 Correct 135 ms 15732 KB Output is correct
6 Correct 144 ms 12872 KB Output is correct
7 Correct 127 ms 16020 KB Output is correct
8 Incorrect 6 ms 6996 KB no wires in direction 1 between segments 94523 and 95348
9 Halted 0 ms 0 KB -

Subtask #5
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 2688 KB Output is correct
2 Correct 2 ms 2644 KB Output is correct
3 Correct 2 ms 2644 KB Output is correct
4 Correct 8 ms 2652 KB Output is correct
5 Incorrect 2 ms 2644 KB no wires in direction 1 between segments 1 and 2
6 Halted 0 ms 0 KB -