oj.uz

Submission #1041606

# Submission time Handle Problem Language Result Execution time Memory
1041606 2024-08-02T06:09:53 Z vjudge1 Tenis (COI19_tenis) C++17
0 / 100
 500 ms 29524 KB 
#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-1][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-1][P]].end())g[a[second_pos][P]].erase(itt);
            }
            swap(a[first_pos][P],a[second_pos][P]);
            swap(first_pos,second_pos);
            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
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 600 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Runtime error 0 ms 488 KB Execution killed with signal 6
5 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 600 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Runtime error 0 ms 488 KB Execution killed with signal 6
5 Halted 0 ms 0 KB -

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 600 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Runtime error 0 ms 488 KB Execution killed with signal 6
5 Halted 0 ms 0 KB -

Subtask #4
0 / 21.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1078 ms 29524 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 600 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Runtime error 0 ms 488 KB Execution killed with signal 6
5 Halted 0 ms 0 KB -