oj.uz

Submission #167308

# Submission time Handle Problem Language Result Execution time Memory
167308 2019-12-07T09:18:31 Z theStaticMind Tenis (COI19_tenis) C++14
30 / 100
 500 ms 14724 KB 
#include<bits/stdc++.h>
#define mp make_pair
#define pb push_back
#define ii pair<int,int>
#define all(x) (x).begin(),(x).end()
#define INF 100000000000000000
#define modulo 1000000007
#define mod 998244353
#define int long long int
using namespace std;
vector<vector<int>> data(3,vector<int>(100005));
vector<vector<int>> arr(3);
vector<int> P(3,0);
vector<vector<int>>adj(100005,vector<int>(3,0));
vector<bool>vis(100005,false);
void dfs(int x){
      vis[x]=true;
      for(int i=0;i<3;i++){
            int y=adj[x][i];
            if(vis[y])continue;
            dfs(y);
      }
}
int32_t main(){
      ios_base::sync_with_stdio(false);
      cin.tie(NULL);
   //   freopen("q.gir","r",stdin);
   //   freopen("q.cik","w",stdout);
      int n,q;
      cin>>n>>q;
      for(int k=0;k<3;k++){
            for(int i=0;i<n;i++){
                  int x;
                  cin>>x;
                  arr[k].pb(x);
                  data[k][x]=i;
                  if(i==0)P[k]=x;
            }
            arr[k].pb(0);
      }
      for(int k=0;k<3;k++)
      for(int i=0;i<n;i++){
            int x=arr[k][i];
            adj[x][k]=arr[k][i+1];
      }
      while(q--){
            int k;
            cin>>k;
            if(k==1){
                  int x;
                  cin>>x;
                  for(int i=1;i<=n;i++)vis[i]=false;
                  bool yes=true;
                  dfs(x);
                  for(int i=1;i<=n;i++)yes=(yes&vis[i]);
                  if(yes)cout<<"DA\n";
                  else cout<<"NE\n";
            }
            else{
                  int p,x,y;
                  cin>>p>>x>>y;p--;
                  swap(arr[p][data[p][x]],arr[p][data[p][y]]);
                  swap(data[p][x],data[p][y]);
                  int X=data[p][x];
                  int Y=data[p][y];
                  adj[x][p]=arr[p][X+1];
                  adj[y][p]=arr[p][Y+1];
                  if(X>0){
                        adj[arr[p][X-1]][p]=x;
                  }
                  if(Y>0){
                        adj[arr[p][Y-1]][p]=y;
                  }
            }
      }

}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 8164 KB Output is correct
2 Correct 14 ms 8168 KB Output is correct
3 Correct 16 ms 8220 KB Output is correct
4 Correct 14 ms 8168 KB Output is correct
5 Correct 14 ms 8168 KB Output is correct
6 Correct 14 ms 8168 KB Output is correct

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 8164 KB Output is correct
2 Correct 14 ms 8168 KB Output is correct
3 Correct 16 ms 8220 KB Output is correct
4 Correct 14 ms 8168 KB Output is correct
5 Correct 14 ms 8168 KB Output is correct
6 Correct 14 ms 8168 KB Output is correct
7 Correct 16 ms 8280 KB Output is correct
8 Correct 15 ms 8292 KB Output is correct
9 Correct 16 ms 8296 KB Output is correct
10 Correct 16 ms 8296 KB Output is correct
11 Correct 16 ms 8292 KB Output is correct
12 Correct 16 ms 8296 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 8164 KB Output is correct
2 Correct 14 ms 8168 KB Output is correct
3 Correct 16 ms 8220 KB Output is correct
4 Correct 14 ms 8168 KB Output is correct
5 Correct 14 ms 8168 KB Output is correct
6 Correct 14 ms 8168 KB Output is correct
7 Correct 16 ms 8280 KB Output is correct
8 Correct 15 ms 8292 KB Output is correct
9 Correct 16 ms 8296 KB Output is correct
10 Correct 16 ms 8296 KB Output is correct
11 Correct 16 ms 8292 KB Output is correct
12 Correct 16 ms 8296 KB Output is correct
13 Correct 92 ms 12868 KB Output is correct
14 Correct 103 ms 12996 KB Output is correct
15 Correct 102 ms 14412 KB Output is correct
16 Correct 106 ms 14184 KB Output is correct
17 Correct 149 ms 14704 KB Output is correct
18 Correct 118 ms 14696 KB Output is correct
19 Correct 133 ms 14696 KB Output is correct
20 Correct 79 ms 11624 KB Output is correct
21 Correct 156 ms 14680 KB Output is correct
22 Correct 166 ms 14700 KB Output is correct

Subtask #4
0 / 21.0

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

Subtask #5
0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 8164 KB Output is correct
2 Correct 14 ms 8168 KB Output is correct
3 Correct 16 ms 8220 KB Output is correct
4 Correct 14 ms 8168 KB Output is correct
5 Correct 14 ms 8168 KB Output is correct
6 Correct 14 ms 8168 KB Output is correct
7 Correct 16 ms 8280 KB Output is correct
8 Correct 15 ms 8292 KB Output is correct
9 Correct 16 ms 8296 KB Output is correct
10 Correct 16 ms 8296 KB Output is correct
11 Correct 16 ms 8292 KB Output is correct
12 Correct 16 ms 8296 KB Output is correct
13 Correct 92 ms 12868 KB Output is correct
14 Correct 103 ms 12996 KB Output is correct
15 Correct 102 ms 14412 KB Output is correct
16 Correct 106 ms 14184 KB Output is correct
17 Correct 149 ms 14704 KB Output is correct
18 Correct 118 ms 14696 KB Output is correct
19 Correct 133 ms 14696 KB Output is correct
20 Correct 79 ms 11624 KB Output is correct
21 Correct 156 ms 14680 KB Output is correct
22 Correct 166 ms 14700 KB Output is correct
23 Execution timed out 1076 ms 14724 KB Time limit exceeded
24 Halted 0 ms 0 KB -