oj.uz

Submission #1041608

# Submission time Handle Problem Language Result Execution time Memory
1041608 2024-08-02T06:11:34 Z vjudge1 Tenis (COI19_tenis) C++17
30 / 100
 500 ms 32320 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][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.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 468 KB Output is correct
6 Correct 1 ms 344 KB Output is correct

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 468 KB Output is correct
6 Correct 1 ms 344 KB Output is correct
7 Correct 1 ms 604 KB Output is correct
8 Correct 2 ms 600 KB Output is correct
9 Correct 1 ms 604 KB Output is correct
10 Correct 1 ms 604 KB Output is correct
11 Correct 1 ms 604 KB Output is correct
12 Correct 1 ms 604 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 468 KB Output is correct
6 Correct 1 ms 344 KB Output is correct
7 Correct 1 ms 604 KB Output is correct
8 Correct 2 ms 600 KB Output is correct
9 Correct 1 ms 604 KB Output is correct
10 Correct 1 ms 604 KB Output is correct
11 Correct 1 ms 604 KB Output is correct
12 Correct 1 ms 604 KB Output is correct
13 Correct 162 ms 30356 KB Output is correct
14 Correct 168 ms 30856 KB Output is correct
15 Correct 206 ms 31056 KB Output is correct
16 Correct 202 ms 30624 KB Output is correct
17 Correct 315 ms 32084 KB Output is correct
18 Correct 228 ms 32320 KB Output is correct
19 Correct 254 ms 31824 KB Output is correct
20 Correct 93 ms 28752 KB Output is correct
21 Correct 317 ms 32080 KB Output is correct
22 Correct 209 ms 31312 KB Output is correct

Subtask #4
0 / 21.0

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

Subtask #5
0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 468 KB Output is correct
6 Correct 1 ms 344 KB Output is correct
7 Correct 1 ms 604 KB Output is correct
8 Correct 2 ms 600 KB Output is correct
9 Correct 1 ms 604 KB Output is correct
10 Correct 1 ms 604 KB Output is correct
11 Correct 1 ms 604 KB Output is correct
12 Correct 1 ms 604 KB Output is correct
13 Correct 162 ms 30356 KB Output is correct
14 Correct 168 ms 30856 KB Output is correct
15 Correct 206 ms 31056 KB Output is correct
16 Correct 202 ms 30624 KB Output is correct
17 Correct 315 ms 32084 KB Output is correct
18 Correct 228 ms 32320 KB Output is correct
19 Correct 254 ms 31824 KB Output is correct
20 Correct 93 ms 28752 KB Output is correct
21 Correct 317 ms 32080 KB Output is correct
22 Correct 209 ms 31312 KB Output is correct
23 Execution timed out 1064 ms 29508 KB Time limit exceeded
24 Halted 0 ms 0 KB -