oj.uz

답안 #744471

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
744471 2023-05-18T15:26:18 Z WKYH 게임 (APIO22_game) C++17
60 / 100
 4000 ms 17924 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);
    //if(u<k)a[v]=max(a[v],u);
    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){
            if(a[f]<u)a[f]=u;
            else continue;
        }
        else{
            if(a[f]<a[u])a[f]=a[u];
            else continue;
        }
        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

# 결과 실행 시간 메모리 Grader output
1 Correct 1 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 0 ms 208 KB Output is correct

Subtask #2
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 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 0 ms 208 KB Output is correct
8 Correct 1 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 0 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 0 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 1 ms 208 KB Output is correct
18 Correct 0 ms 208 KB Output is correct
19 Correct 0 ms 208 KB Output is correct

Subtask #3
18.0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 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 0 ms 208 KB Output is correct
8 Correct 1 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 0 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 0 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 1 ms 208 KB Output is correct
18 Correct 0 ms 208 KB Output is correct
19 Correct 0 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 328 KB Output is correct
23 Correct 2 ms 336 KB Output is correct
24 Correct 4 ms 336 KB Output is correct
25 Correct 5 ms 336 KB Output is correct
26 Correct 3 ms 336 KB Output is correct
27 Correct 7 ms 336 KB Output is correct
28 Correct 4 ms 448 KB Output is correct
29 Correct 4 ms 336 KB Output is correct

Subtask #4
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 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 0 ms 208 KB Output is correct
8 Correct 1 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 0 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 0 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 1 ms 208 KB Output is correct
18 Correct 0 ms 208 KB Output is correct
19 Correct 0 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 328 KB Output is correct
23 Correct 2 ms 336 KB Output is correct
24 Correct 4 ms 336 KB Output is correct
25 Correct 5 ms 336 KB Output is correct
26 Correct 3 ms 336 KB Output is correct
27 Correct 7 ms 336 KB Output is correct
28 Correct 4 ms 448 KB Output is correct
29 Correct 4 ms 336 KB Output is correct
30 Correct 24 ms 1580 KB Output is correct
31 Correct 12 ms 1360 KB Output is correct
32 Correct 33 ms 2040 KB Output is correct
33 Correct 18 ms 1948 KB Output is correct
34 Correct 635 ms 2016 KB Output is correct
35 Correct 273 ms 2096 KB Output is correct
36 Correct 58 ms 1932 KB Output is correct
37 Correct 68 ms 1940 KB Output is correct
38 Correct 86 ms 1712 KB Output is correct
39 Correct 67 ms 1824 KB Output is correct
40 Correct 553 ms 2164 KB Output is correct
41 Correct 161 ms 1952 KB Output is correct
42 Correct 131 ms 1868 KB Output is correct
43 Correct 81 ms 2064 KB Output is correct
44 Correct 419 ms 2080 KB Output is correct

Subtask #5
0.0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 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 0 ms 208 KB Output is correct
8 Correct 1 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 0 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 0 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 1 ms 208 KB Output is correct
18 Correct 0 ms 208 KB Output is correct
19 Correct 0 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 328 KB Output is correct
23 Correct 2 ms 336 KB Output is correct
24 Correct 4 ms 336 KB Output is correct
25 Correct 5 ms 336 KB Output is correct
26 Correct 3 ms 336 KB Output is correct
27 Correct 7 ms 336 KB Output is correct
28 Correct 4 ms 448 KB Output is correct
29 Correct 4 ms 336 KB Output is correct
30 Correct 24 ms 1580 KB Output is correct
31 Correct 12 ms 1360 KB Output is correct
32 Correct 33 ms 2040 KB Output is correct
33 Correct 18 ms 1948 KB Output is correct
34 Correct 635 ms 2016 KB Output is correct
35 Correct 273 ms 2096 KB Output is correct
36 Correct 58 ms 1932 KB Output is correct
37 Correct 68 ms 1940 KB Output is correct
38 Correct 86 ms 1712 KB Output is correct
39 Correct 67 ms 1824 KB Output is correct
40 Correct 553 ms 2164 KB Output is correct
41 Correct 161 ms 1952 KB Output is correct
42 Correct 131 ms 1868 KB Output is correct
43 Correct 81 ms 2064 KB Output is correct
44 Correct 419 ms 2080 KB Output is correct
45 Correct 462 ms 14248 KB Output is correct
46 Correct 21 ms 8784 KB Output is correct
47 Correct 25 ms 8804 KB Output is correct
48 Correct 563 ms 17924 KB Output is correct
49 Correct 564 ms 17872 KB Output is correct
50 Execution timed out 4054 ms 14376 KB Time limit exceeded
51 Halted 0 ms 0 KB -