oj.uz

Submission #740312

# Submission time Handle Problem Language Result Execution time Memory
740312 2023-05-12T09:48:25 Z WKYH Game (APIO22_game) C++17
30 / 100
 4000 ms 2248 KB 
#include<bits/stdc++.h>
#define qc ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define rt return
#define fi first
#define se second
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define vecin(a) for(auto &d:a)cin>>d;
typedef long long int ll;
const long long mod=1e9+7;
const int int_inf=2147483647;
const long long int ll_inf=9223372036854775807;
const int alp_up=64;
const int alp_lw=96;
int dx[]={-1,-1,0,1,1,1,0,-1};
int dy[]={0,1,1,1,0,-1,-1,-1};
using namespace std;
ll gcd(ll a,ll b){if(b==0)rt a;rt gcd(b,a%b);}
ll lcm(ll a,ll b){rt a/gcd(a,b)*b;}
void setIO(string name)
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    freopen((name+".in").c_str(),"r",stdin);
    freopen((name+".out").c_str(),"w",stdout);
}

/*
int n;
vector<int>h;
vector<vector<int>>l,r,low,hgh;
void init(int N,vector<int>H)
{
    n=N;h=H;
    l.resize(20,vector<int>(n,-1));
    r.resize(20,vector<int>(n,-1));
    low.resize(20,vector<int>(n,-1));
    hgh.resize(20,vector<int>(n,-1));
    // monotonic stack for l and r
        // -1 means no target
    stack<int>s;
    for(int i=0;i<n;i++)
    {
        while(!s.empty()&&h[s.top()]<h[i])s.pop();
        if(!s.empty())l[0][i]=s.top();
        s.push(i);
    }
    while(!s.empty())s.pop();
    for(int i=n-1;i>=0;i--)
    {
        while(!s.empty()&&h[s.top()]<h[i])s.pop();
        if(!s.empty())r[0][i]=s.top();
        s.push(i);
    }
    // sparse table for l and r
    for(int i=1;i<20;i++){
        for(int j=0;j<n;j++){
            if(l[i-1][j]!=-1)l[i][j]=l[i-1][l[i-1][j]];
            if(r[i-1][j]!=-1)r[i][j]=r[i-1][r[i-1][j]];
        }
    }
    // sparse table for low and hgh
        // using dynamic programming
    for(int i=0;i<n;i++){
        if(l[0][i]==-1)hgh[0][i]=r[0][i];
        else if(r[0][i]==-1)hgh[0][i]=l[0][i];
        else if(h[l[0][i]]>h[r[0][i]]){
            hgh[0][i]=l[0][i];
            low[0][i]=r[0][i];
        }
        else{
            hgh[0][i]=r[0][i];
            low[0][i]=l[0][i];
        }
    }
    for(int i=1;i<20;i++){
        for(int j=0;j<n;j++){
            if(low[i-1][j]!=-1)low[i][j]=low[i-1][low[i-1][j]];
            if(hgh[i-1][j]!=-1)hgh[i][j]=hgh[i-1][hgh[i-1][j]];
        }
    }
    //for(auto c:l)cout<<c<<" ";cout<<"\n";
    //for(auto c:r)cout<<c<<" ";cout<<"\n";
    //for(auto c:tall){for(auto d:c)cout<<d<<" ";cout<<"\n";}
}
int tallest(int cur,int tar) // tallest tree in [cur,tar]
{
    for(int i=19;i>=0;i--){
        if(r[i][cur]==-1)continue;
        if(r[i][cur]>tar)continue;
        cur=r[i][cur];
    }
    rt cur;
}
int minimum_jumps(int a,int b,int c,int d)
{
    if(b+1==c)rt (r[0][b]<=d&&r[0][b]!=-1)? 1:-1; // no tree in [b+1,c-1]

    int t_cd=tallest(c,d); //tallest tree in [c,d]
    int t_bc=tallest(b+1,c-1); // tallest tree in [b+1,c-1]
    int cur=b,ans=0;

    // tallest tree from b to left, not higher than t_cd
    for(int i=19;i>=0;i--){
        if(l[i][cur]==-1)continue;
        if(l[i][cur]<a)continue;
        if(h[l[i][cur]]>h[t_cd])continue;
        cur=l[i][cur];
    }
    if(h[cur]>h[t_bc]){ // straight away jump to [c,d]
        rt (r[0][cur]<=d&&r[0][cur]!=-1)? 1:-1;
    }

    // choose higher edge to jump, not higher than h[t_bc]
    for(int i=19;i>=0;i--){
        if(hgh[i][cur]==-1)continue;
        if(h[hgh[i][cur]]>h[t_bc])continue;
        cur=hgh[i][cur];
        ans+=(1<<i);
    }
    if(cur==t_bc)rt (r[0][cur]<=d&&r[0][cur]!=-1)? ans+1:-1;

    // any jump will cause h[cur] > h[t_bc]
    if(l[0][cur]!=-1&&c<=r[0][l[0][cur]]&&r[0][l[0][cur]]<=d)rt ans+2; // consider left
    for(int i=19;i>=0;i--){ // consider right
        if(r[i][cur]==-1)continue;
        if(c<=r[i][cur])continue;
        cur=r[i][cur];
        ans+=(1<<i);
    }

    // jump to right suppose in [c,d]
    cur=r[0][cur];ans++;
    rt (c<=cur&&cur<=d)? ans:-1;
}

int xmain()
{
    init(7, {3, 2, 1, 6, 4, 5, 7});cout<<minimum_jumps(4, 4, 6, 6)<<" "<<minimum_jumps(1, 3, 5, 6)<<" "<<minimum_jumps(0, 1, 2, 2);
    //init(5,{5,1,2,3,4});cout<<minimum_jumps(1,1,4,4);
    //init(9,{9,6,4,2,1,3,5,7,8});cout<<minimum_jumps(0,0,1,1);
    //init(8,{1,2,3,4,5,6,7,8}); cout<<minimum_jumps(0,2,4,7);
    cout<<"\n";
    for(int i=0;i<9;i++){for(int j=i+1;j<9;j++)cout<<minimum_jumps(i,i,j,j)<<" ";cout<<"\n";}

    rt 0;
}
/*/

int n,k;
vector<vector<int>>edge;
vector<int>a;
void init(int N,int K)
{
    n=N,k=K;
    edge.resize(n);
    a.resize(n,-1);
    for(int i=0;i<k-1;i++){
        edge[i].push_back(i+1);
    }
    //for(int i=1;i<n;i++)a[i]=i;
}
int add_teleporter(int u,int v)
{
    edge[u].push_back(v);
    queue<int>q;
    vector<bool>vis(n,0);
    q.push(v);vis[v]=1;
    while(!q.empty()){
        int f=q.front();
        q.pop();
        if(u<k)a[f]=max(a[f],u);
        else a[f]=max(a[f],a[u]);
        for(auto c:edge[f]){
            if(vis[c])continue;
            q.push(c);vis[c]=1;
        }
    }
    for(int i=0;i<k;i++){
        if(i<=a[i]&&a[i]<k)rt 1;
    }
    rt 0;
}
int xmain()
{
    //init(6,3);cout<<add_teleporter(3,4)<<add_teleporter(5,0)<<add_teleporter(4,5)<<add_teleporter(5,3)<<add_teleporter(1,4);
    //init(6,3);cout<<add_teleporter(5,0)<<add_teleporter(1,4)<<add_teleporter(2,4)<<add_teleporter(4,5);
    //init(6,6);for(int i=2;i<6;i++)for(int j=i+1;j<6;j++)cout<<add_teleporter(j,i);
    init(5,1);cout<<add_teleporter(0,2)<<add_teleporter(3,0)<<add_teleporter(3,2)<<add_teleporter(2,3);
    rt 0;
}

//*/

Compilation message

game.cpp: In function 'void setIO(std::string)':
game.cpp:24:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   24 |     freopen((name+".in").c_str(),"r",stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
game.cpp:25:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   25 |     freopen((name+".out").c_str(),"w",stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
2.0 / 2.0

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

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 208 KB Output is correct
2 Correct 0 ms 208 KB Output is correct
3 Correct 1 ms 208 KB Output is correct
4 Correct 1 ms 208 KB Output is correct
5 Correct 1 ms 208 KB Output is correct
6 Correct 1 ms 208 KB Output is correct
7 Correct 1 ms 208 KB Output is correct
8 Correct 0 ms 208 KB Output is correct
9 Correct 0 ms 208 KB Output is correct
10 Correct 0 ms 208 KB Output is correct
11 Correct 1 ms 208 KB Output is correct
12 Correct 1 ms 208 KB Output is correct
13 Correct 1 ms 208 KB Output is correct
14 Correct 1 ms 208 KB Output is correct
15 Correct 1 ms 208 KB Output is correct
16 Correct 1 ms 208 KB Output is correct
17 Correct 0 ms 208 KB Output is correct
18 Correct 1 ms 208 KB Output is correct
19 Correct 1 ms 208 KB Output is correct

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 208 KB Output is correct
2 Correct 0 ms 208 KB Output is correct
3 Correct 1 ms 208 KB Output is correct
4 Correct 1 ms 208 KB Output is correct
5 Correct 1 ms 208 KB Output is correct
6 Correct 1 ms 208 KB Output is correct
7 Correct 1 ms 208 KB Output is correct
8 Correct 0 ms 208 KB Output is correct
9 Correct 0 ms 208 KB Output is correct
10 Correct 0 ms 208 KB Output is correct
11 Correct 1 ms 208 KB Output is correct
12 Correct 1 ms 208 KB Output is correct
13 Correct 1 ms 208 KB Output is correct
14 Correct 1 ms 208 KB Output is correct
15 Correct 1 ms 208 KB Output is correct
16 Correct 1 ms 208 KB Output is correct
17 Correct 0 ms 208 KB Output is correct
18 Correct 1 ms 208 KB Output is correct
19 Correct 1 ms 208 KB Output is correct
20 Correct 1 ms 336 KB Output is correct
21 Correct 1 ms 208 KB Output is correct
22 Correct 1 ms 336 KB Output is correct
23 Correct 1 ms 336 KB Output is correct
24 Correct 5 ms 336 KB Output is correct
25 Correct 21 ms 356 KB Output is correct
26 Correct 17 ms 332 KB Output is correct
27 Correct 5 ms 352 KB Output is correct
28 Correct 11 ms 344 KB Output is correct
29 Correct 20 ms 364 KB Output is correct

Subtask #4
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 208 KB Output is correct
2 Correct 0 ms 208 KB Output is correct
3 Correct 1 ms 208 KB Output is correct
4 Correct 1 ms 208 KB Output is correct
5 Correct 1 ms 208 KB Output is correct
6 Correct 1 ms 208 KB Output is correct
7 Correct 1 ms 208 KB Output is correct
8 Correct 0 ms 208 KB Output is correct
9 Correct 0 ms 208 KB Output is correct
10 Correct 0 ms 208 KB Output is correct
11 Correct 1 ms 208 KB Output is correct
12 Correct 1 ms 208 KB Output is correct
13 Correct 1 ms 208 KB Output is correct
14 Correct 1 ms 208 KB Output is correct
15 Correct 1 ms 208 KB Output is correct
16 Correct 1 ms 208 KB Output is correct
17 Correct 0 ms 208 KB Output is correct
18 Correct 1 ms 208 KB Output is correct
19 Correct 1 ms 208 KB Output is correct
20 Correct 1 ms 336 KB Output is correct
21 Correct 1 ms 208 KB Output is correct
22 Correct 1 ms 336 KB Output is correct
23 Correct 1 ms 336 KB Output is correct
24 Correct 5 ms 336 KB Output is correct
25 Correct 21 ms 356 KB Output is correct
26 Correct 17 ms 332 KB Output is correct
27 Correct 5 ms 352 KB Output is correct
28 Correct 11 ms 344 KB Output is correct
29 Correct 20 ms 364 KB Output is correct
30 Correct 24 ms 1668 KB Output is correct
31 Correct 13 ms 1232 KB Output is correct
32 Correct 32 ms 1952 KB Output is correct
33 Correct 32 ms 2160 KB Output is correct
34 Correct 607 ms 2060 KB Output is correct
35 Correct 2622 ms 2200 KB Output is correct
36 Correct 1225 ms 2012 KB Output is correct
37 Correct 710 ms 2072 KB Output is correct
38 Correct 942 ms 1920 KB Output is correct
39 Correct 844 ms 1820 KB Output is correct
40 Correct 898 ms 2248 KB Output is correct
41 Correct 2984 ms 2088 KB Output is correct
42 Correct 1065 ms 1980 KB Output is correct
43 Execution timed out 4014 ms 2088 KB Time limit exceeded
44 Halted 0 ms 0 KB -

Subtask #5
0.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 208 KB Output is correct
2 Correct 0 ms 208 KB Output is correct
3 Correct 1 ms 208 KB Output is correct
4 Correct 1 ms 208 KB Output is correct
5 Correct 1 ms 208 KB Output is correct
6 Correct 1 ms 208 KB Output is correct
7 Correct 1 ms 208 KB Output is correct
8 Correct 0 ms 208 KB Output is correct
9 Correct 0 ms 208 KB Output is correct
10 Correct 0 ms 208 KB Output is correct
11 Correct 1 ms 208 KB Output is correct
12 Correct 1 ms 208 KB Output is correct
13 Correct 1 ms 208 KB Output is correct
14 Correct 1 ms 208 KB Output is correct
15 Correct 1 ms 208 KB Output is correct
16 Correct 1 ms 208 KB Output is correct
17 Correct 0 ms 208 KB Output is correct
18 Correct 1 ms 208 KB Output is correct
19 Correct 1 ms 208 KB Output is correct
20 Correct 1 ms 336 KB Output is correct
21 Correct 1 ms 208 KB Output is correct
22 Correct 1 ms 336 KB Output is correct
23 Correct 1 ms 336 KB Output is correct
24 Correct 5 ms 336 KB Output is correct
25 Correct 21 ms 356 KB Output is correct
26 Correct 17 ms 332 KB Output is correct
27 Correct 5 ms 352 KB Output is correct
28 Correct 11 ms 344 KB Output is correct
29 Correct 20 ms 364 KB Output is correct
30 Correct 24 ms 1668 KB Output is correct
31 Correct 13 ms 1232 KB Output is correct
32 Correct 32 ms 1952 KB Output is correct
33 Correct 32 ms 2160 KB Output is correct
34 Correct 607 ms 2060 KB Output is correct
35 Correct 2622 ms 2200 KB Output is correct
36 Correct 1225 ms 2012 KB Output is correct
37 Correct 710 ms 2072 KB Output is correct
38 Correct 942 ms 1920 KB Output is correct
39 Correct 844 ms 1820 KB Output is correct
40 Correct 898 ms 2248 KB Output is correct
41 Correct 2984 ms 2088 KB Output is correct
42 Correct 1065 ms 1980 KB Output is correct
43 Execution timed out 4014 ms 2088 KB Time limit exceeded
44 Halted 0 ms 0 KB -