Submission #1041730

#	Time	Username	Problem	Language	Result	Execution time	Memory
1041730		vjudge1	Tenis (COI19_tenis)	C++17	28 / 100	39 ms	5336 KiB

tenis

                                    ///~~~LOTA~~~///
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define append push_back
#define add insert
#define nl '\n'
#define ff first
#define ss second
#define pii pair<int,int>
#define pll pair<ll,ll>
#define all(x) (x).begin(),(x).end()
#define L0TA ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
#define terminator main
#define N 100001
int n;
int h[N];
int x[N];
int P[N][4];
int F[N][4];
bool vis[N];
void dfs(int v){
    if(vis[v]) return;
    vis[v]=1;
    for(int i=1;i<4;i++)
        dfs(F[v][i]);
}
bool query(int x){
    for(int i=1;i<=n;i++)
        vis[i]=0;
    dfs(x);
    for(int i=1;i<=n;i++){
        if(!vis[i]) return 0;
    }
    return 1;
}
void solve(int m){
    vector<int> v;
    for(int i=1;i<=n;i++){
        if(!P[i][1]) v.append(i);
    }
    for(int i=h[v[0]]=0;i<n-1;i++){
        v.append(F[v[i]][1]);
        h[v[i+1]]=i+1;
    }
    h[0]=n;
    for(int i=n-1;i>=0;i--){
        x[i]=i;
        if(i<n-1) 
            x[i]=min(x[i],x[i+1]);
        x[i]=min(x[i],h[F[v[i]][2]]);
        x[i]=min(x[i],h[F[v[i]][3]]);
    }
    for(int i=0;i<n;i++)
        x[i]=x[x[i]];
    int p,q;
    while(m--){
        cin>>p>>q;
        if(x[h[q]])
            cout<<"NE\n";
        else cout<<"DA\n";
    }
}
void solve(){
    int m,o,p,q,r;
    cin>>n>>m;
    for(int j=1;j<4;j++){
        cin>>p;
        for(int i=1;i<n;i++){
            cin>>q;
            P[q][j]=p;
            F[p][j]=q;
            p=q;
        }
    }
    if(m>10){
        solve(m);
        return;
    }
    vis[0]=1;
    while(m--){
        cin>>o;
        if(o>1){
            cin>>r>>p>>q;
            if(F[q][r]==p)
                swap(p,q);
            if(F[p][r]==q){
                P[q][r]=P[p][r];
                F[p][r]=F[q][r];
                F[q][r]=p;
                P[p][r]=q;
                P[F[p][r]][r]=p;
                F[P[q][r]][r]=q;
            }
            else{
                swap(P[p][r],P[q][r]);
                swap(F[p][r],F[q][r]);
                swap(P[F[p][r]],P[F[q][r]]);
                swap(F[P[p][r]],F[P[q][r]]);
            }
        }
        else{
            cin>>r;
            if(query(r))
                cout<<"DA\n";
            else cout<<"NE\n";
        }
    }
}
int terminator(){
    L0TA;
    solve();
    return 0;
}

• Subtask 1: 7 / 7
• Subtask 2: 0 / 11
• Subtask 3: 0 / 12
• Subtask 4: 21 / 21
• Subtask 5: 0 / 49