oj.uz

답안 #566406

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
566406 2022-05-22T09:50:38 Z BJoozz Alternating Current (BOI18_alternating) C++17
0 / 100
 3 ms 2772 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;
}
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()){
        int p = Q.front();Q.pop();
        for(int u:pr[p]){
            u=R[u];
            if(in[u]){
                if(!in[p] && good[u]){
                    pd=ii(p,L[u]);
                    dich=p;break;
                }
                continue;
            }
            if(!vs[u]){
                vs[u]=1;trace[u]=ii(p,L[u]);
                Q.push(u);
            }
        }
        if(ok[L[p]] && !vs[L[p]] && L[p]!=trace[p].X){
            vs[L[p]]=1;
            trace[L[p]]=trace[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';
}

Compilation message

alternating.cpp: In function 'int main()':
alternating.cpp:30:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   30 |     freopen("Alternating Current.inp","r",stdin);freopen("Alternating Current.out","w",stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
alternating.cpp:30:57: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   30 |     freopen("Alternating Current.inp","r",stdin);freopen("Alternating Current.out","w",stdout);
      |                                                  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 3 ms 2772 KB Unexpected end of file - token expected
2 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 3 ms 2772 KB Unexpected end of file - token expected
2 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 3 ms 2772 KB Unexpected end of file - token expected
2 Halted 0 ms 0 KB -

Subtask #4
0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 3 ms 2772 KB Unexpected end of file - token expected
2 Halted 0 ms 0 KB -

Subtask #5
0 / 26.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 3 ms 2772 KB Unexpected end of file - token expected
2 Halted 0 ms 0 KB -