oj.uz

Submission #830464

# Submission time Handle Problem Language Result Execution time Memory
830464 2023-08-19T06:51:54 Z Amylopectin Prize (CEOI22_prize) C++14
0 / 100
 1940 ms 605568 KB 
#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
const int mxn = 2e6 + 10,mxm = 2e6 + 10;
vector<int> pat[2][mxn] = {};
int par[2][mxn] = {},he[2] = {},retva,retbn,retan,le[2] = {},ri[2] = {}
,up[2][25][mxn] = {},ju[2][25][mxn] = {},u[mxn] = {},las[2],ans[2];
int re(int v,int cn,int ro)
{
    int i,j,fn,can = -1,cbn = -1,cva = 0,of = 0;
    if(u[cn] == 1)
    {
        can = cn;
        cbn = cn;
        cva = 0;
    }
    for(i=0; i<pat[v][cn].size(); i++)
    {
        fn = pat[v][cn][i];
        re(v,fn,ro);
        if(retan != -1)
        {
            if(can == -1)
            {
                can = retan;
                cbn = retbn;
                cva = retva;
            }
            else 
            {
                of = 1;
                if(ro == 0)
                {
                    printf("? %d %d\n",can,retan);
                }
                else 
                {
                    scanf("%d %d %d %d",&le[0],&ri[0],&le[1],&ri[1]);
                    ju[v][0][cbn] = cn;
                    ju[v][0][retbn] = cn;
                    las[v] = cn;
                    up[v][0][cbn] = le[v] - cva;
                    up[v][0][retbn] = ri[v] - retva;
                }
            }
        }
    }
    if(of == 1)
    {
        retan = can;
        retva = cva + up[v][0][cbn];
        retbn = cn;
    }
    else 
    {
        retan = can;
        retva = cva;
        retbn = cbn;
    }
    return 0;
}
int main()
{
    int i,j,n,m,q,t,cn,cm,fn,fm,k;
    scanf("%d %d %d %d",&n,&m,&q,&t);
    for(i=0; i<2; i++)
    {
        for(j=1; j<=n; j++)
        {
            scanf("%d",&par[i][j]);
            if(par[i][j] == -1)
            {
                he[i] = j;
            }
            else 
            {
                pat[i][par[i][j]].push_back(j);
            }
        }
    }
    for(i=1; i<=m; i++)
    {
        printf("%d ",i);
        u[i] = 1;
    }
    printf("\n");
    re(0,he[0],0);
    re(1,he[1],0);
    printf("!\n");
    fflush(stdout);
    re(0,he[0],1);
    re(1,he[1],1);
    ju[0][0][las[0]] = -1;
    ju[1][0][las[1]] = -1;
    for(i=0; i<22; i++)
    {
        for(j=1; j<=n; j++)
        {
            for(k=0; k<2; k++)
            {
                if(ju[k][i][j] == -1)
                {
                    ju[k][i+1][j] = -1;
                    up[k][i+1][j] = -1;
                } 
                else 
                {
                    ju[k][i+1][j] = ju[k][i][ju[k][i][j]];
                    up[k][i+1][j] = up[k][i][ju[k][i][j]] + up[k][i][j];
                }
            }
        }
    }
    for(i=0; i<t; i++)
    {
        scanf("%d %d",&cn,&cm);
        for(k=0; k<2; k++)
        {
            ans[k] = 0;
            fn = cn;
            fm = cm;
            for(j=20; j>=0; j--)
            {
                if(ju[k][j][fn] != ju[k][j][fm])
                {
                    ans[k] += up[k][j][fn] + up[k][j][fm];
                    fn = ju[k][j][fn];
                    fm = ju[k][j][fm];
                }
            }
            ans[k] += up[k][0][fn] + up[k][0][fm];
        }
        printf("%d %d\n",ans[0],ans[1]);
    }
}

Compilation message

Main.cpp: In function 'int re(int, int, int)':
Main.cpp:19:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   19 |     for(i=0; i<pat[v][cn].size(); i++)
      |              ~^~~~~~~~~~~~~~~~~~
Main.cpp:12:11: warning: unused variable 'j' [-Wunused-variable]
   12 |     int i,j,fn,can = -1,cbn = -1,cva = 0,of = 0;
      |           ^
Main.cpp:40:26: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   40 |                     scanf("%d %d %d %d",&le[0],&ri[0],&le[1],&ri[1]);
      |                     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp: In function 'int main()':
Main.cpp:67:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   67 |     scanf("%d %d %d %d",&n,&m,&q,&t);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:72:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   72 |             scanf("%d",&par[i][j]);
      |             ~~~~~^~~~~~~~~~~~~~~~~
Main.cpp:118:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  118 |         scanf("%d %d",&cn,&cm);
      |         ~~~~~^~~~~~~~~~~~~~~~~

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 966 ms 350648 KB Time limit exceeded (wall clock)
2 Halted 0 ms 0 KB -

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Execution timed out 967 ms 351232 KB Time limit exceeded (wall clock)
2 Halted 0 ms 0 KB -

Subtask #3
0 / 19.0

# Verdict Execution time Memory Grader output
1 Execution timed out 832 ms 349452 KB Time limit exceeded (wall clock)
2 Halted 0 ms 0 KB -

Subtask #4
0 / 22.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1868 ms 603832 KB Time limit exceeded (wall clock)
2 Halted 0 ms 0 KB -

Subtask #5
0 / 24.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1940 ms 605568 KB Time limit exceeded (wall clock)
2 Halted 0 ms 0 KB -