oj.uz

Submission #1066404

# Submission time Handle Problem Language Result Execution time Memory
1066404 2024-08-19T20:41:25 Z Dennis_Jason Cat Exercise (JOI23_ho_t4) C++14
0 / 100
 2 ms 5032 KB 
#include <bitset>
#include <cmath>
#include <functional>
#include <algorithm>
#include <numeric>
#include <deque>
#include <fstream>
#include <iomanip>
#include <iostream>
#include <iterator>
#include <limits>
#include <list>
#include <map>
#include <unordered_map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>
#include <cstring>
#include <climits>
#define pb push_back
#define MOD 1000000007
#define NMAX 200001
#define nl '\n'
#define INF 1000000007
#define pii1 pair<int, pair<int,int>>  (1,(1,2));
#define pii pair<int,int>
#define tpl tuple<int,int,int,int,int>
using namespace std;
ifstream fin("data.in");
ofstream fout("data.out");
/*
    ====================DEMONSTRATION======================

        n=2
        1....#####..##
        ....##########
        ####..........
        ##########....
        ##########....
        1....####....#
    =========================END===========================

 */
int n;
vector<int>v;
vector<vector<int>>G(NMAX);
int start;
bool vis_s[NMAX],vis_d[NMAX];
int maxi[NMAX];
signed main() {

     cin>>n;
     v.resize(n+1);
     map<int,int>mp;
     for(int i=1;i<=n;++i) {
         cin >> v[i];
         if (v[i] == n)
             start = i;
         mp[v[i]]=i;
     }
     for(int i=1;i<n;++i)
     {
         int x,y;
         cin>>x>>y;
         G[x].pb(y);
         G[y].pb(x);
     }
     for (int i = 1; i < start; ++i)
         vis_s[i] = 1;

     for(int i=start+1;i<=n;++i)
             vis_d[i]=1;
     int i=start;
     int ans_s=0;
     while(!(v[i-1]>v[i] && v[i]<v[i+1]) && i>0)
     {
         int aux=v[i];
         vis_s[mp[aux]]=1;
         while(vis_s[mp[aux]])
             aux--;
//         cout<<i<<" "<<aux<<" "<<abs(i-mp[aux])<<nl;
         ans_s+=abs(i-mp[aux]);
         i=mp[aux];
     }
     int ans=0;
    i=start;
    int ans_d=0;
    while(!(v[i-1]>v[i] && v[i]<v[i+1]) && i>0)
    {
        int aux=v[i];
        vis_d[mp[aux]]=1;
        while(vis_d[mp[aux]])
            aux--;
//         cout<<i<<" "<<aux<<" "<<abs(i-mp[aux])<<nl;
        ans_d+=abs(i-mp[aux]);
        i=mp[aux];
    }
    int ans_mid=0;
    while(!(v[i-1]>v[i] && v[i]<v[i+1]) && i>0)
    {
        int aux=v[i];
        ans_mid+=(abs(i-mp[aux-1]));
        i=mp[aux-1];
    }
    ans=max({ans_s,ans_d,ans_mid});
     cout<<ans;







    return 0;
}

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4956 KB Output is correct
2 Correct 2 ms 4956 KB Output is correct
3 Correct 1 ms 4956 KB Output is correct
4 Correct 1 ms 4956 KB Output is correct
5 Correct 1 ms 4956 KB Output is correct
6 Incorrect 2 ms 5032 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4956 KB Output is correct
2 Correct 2 ms 4956 KB Output is correct
3 Correct 1 ms 4956 KB Output is correct
4 Correct 1 ms 4956 KB Output is correct
5 Correct 1 ms 4956 KB Output is correct
6 Incorrect 2 ms 5032 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4956 KB Output is correct
2 Correct 2 ms 4956 KB Output is correct
3 Correct 1 ms 4956 KB Output is correct
4 Correct 1 ms 4956 KB Output is correct
5 Correct 1 ms 4956 KB Output is correct
6 Incorrect 2 ms 5032 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4956 KB Output is correct
2 Correct 2 ms 4956 KB Output is correct
3 Correct 1 ms 4956 KB Output is correct
4 Correct 1 ms 4956 KB Output is correct
5 Correct 1 ms 4956 KB Output is correct
6 Incorrect 2 ms 5032 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4956 KB Output is correct
2 Correct 2 ms 4956 KB Output is correct
3 Correct 1 ms 4956 KB Output is correct
4 Correct 1 ms 4956 KB Output is correct
5 Correct 1 ms 4956 KB Output is correct
6 Incorrect 2 ms 5032 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4952 KB Output is correct
2 Incorrect 1 ms 4952 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #7
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4956 KB Output is correct
2 Correct 2 ms 4956 KB Output is correct
3 Correct 1 ms 4956 KB Output is correct
4 Correct 1 ms 4956 KB Output is correct
5 Correct 1 ms 4956 KB Output is correct
6 Incorrect 2 ms 5032 KB Output isn't correct
7 Halted 0 ms 0 KB -