Submission #1041608

#	Time	Username	Problem	Language	Result	Execution time	Memory
1041608		vjudge1	Tenis (COI19_tenis)	C++17	30 / 100	1064 ms	32320 KiB

tenis

#include<bits/stdc++.h>
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx")
using namespace std;
#define int long long 
const int N = 100001;
const int mod = 1e9+7;
const int mod1 = 998244353;
map<int,multiset<int>> g;
vector<bool> vis(N);
void dfs(int node){
    if(vis[node])return;
    vis[node] = true;
    for(int child:g[node]){
        dfs(child);
    }
}
void solve(){
    int n,q;cin >> n >> q;
    int a[n+1][4];
    for(int i = 1;i<=n ; i++)
        cin >> a[i][1];
    for(int i = 1;i<=n ;i ++)
        cin >> a[i][2];
    for(int i = 1;i<=n ;i ++)
        cin >> a[i][3];
    for(int i = 2; i<=n ;i ++){
        g[a[i-1][1]].insert(a[i][1]);
        g[a[i-1][2]].insert(a[i][2]);
        g[a[i-1][3]].insert(a[i][3]);
    }
    for(int its = 0 ;its <q ;its ++){
        int it ;cin >> it;
        if(it == 1){
            int X;cin >> X;
            for(int i = 1;i<=n ;i++)vis[i] =false;
            dfs(X);bool f= true;
            for(int i = 1;i<=n ; i++){
                if(!vis[i])f=false;
            }
            if(f)cout<<"DA"<<endl;
            else cout<<"NE"<<endl;
        }
        else{
            int P,A,B;cin >> P >> A >> B;
            int first_pos = -1;
            int second_pos = -1;
            for(int i = 1;i<=n ;i ++){
                if(a[i][P] == A)first_pos = i;
                if(a[i][P] == B)second_pos = i;
            }
            if(first_pos>1){
                auto itt = g[a[first_pos-1][P]].find(a[first_pos][P]);
                if(itt!=g[a[first_pos-1][P]].end())g[a[first_pos-1][P]].erase(itt);
            }
            if(first_pos<n){
                auto itt = g[a[first_pos][P]].find(a[first_pos+1][P]);
                if(itt!=g[a[first_pos][P]].end())g[a[first_pos][P]].erase(itt);
            }
            if(second_pos>1){
                auto itt = g[a[second_pos-1][P]].find(a[second_pos][P]);
                if(itt!=g[a[second_pos-1][P]].end())g[a[second_pos-1][P]].erase(itt);
            }
            if(second_pos<n){
                auto itt = g[a[second_pos][P]].find(a[second_pos+1][P]);
                if(itt!=g[a[second_pos][P]].end())g[a[second_pos][P]].erase(itt);
            }
            swap(a[first_pos][P],a[second_pos][P]);
            if(first_pos>1){
                g[a[first_pos-1][P]].insert(a[first_pos][P]);
            }
            if(first_pos<n){
                g[a[first_pos][P]].insert(a[first_pos+1][P]);
            }
            if(second_pos>1){
                g[a[second_pos-1][P]].insert(a[second_pos][P]);
            }
            if(second_pos<n){
                g[a[second_pos][P]].insert(a[second_pos+1][P]);
            }
        }

    }
}
signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);cout.tie(NULL);
    
    int t=1;
    // cin>>t;
    cout<<setprecision(16);
    while(t--){
        solve();
    }
}

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