Submission #1161822

#	Time	Username	Problem	Language	Result	Execution time	Memory
1161822		modwwe	Park (JOI17_park)	C++20	100 / 100	413 ms	4584 KiB

park

#include "park.h"
#pragma GCC optimize("Ofast,unroll-loops")
#include<bits/stdc++.h>
//#define int   long long
#define ll long long
#define down cout<<'\n';
#define debug cout<<" cucuucucuuu",down
#define modwwe  int t;cin>>t; while(t--)
#define bit(i,j) (i>>j&1)
#define sobit(a) __builtin_popcountll(a)
#define task2 "top1tst"
#define task "test"
#define fin(x) freopen(x".inp","r",stdin)
#define fou(x) freopen(x".out","w",stdout)
#define pb push_back
#define mask(k) (1ll<<k)
#define checktime   cerr << (double)clock() / CLOCKS_PER_SEC * 1000  << " ms";
using namespace std;
#define getchar_unlocked getchar
mt19937 rd(chrono::steady_clock::now().time_since_epoch().count());
int rand(int l,int r)
{
    return uniform_int_distribution<int>(l,r)(rd);
}
void phongbeo();
const int inf=1e17;
const int mod2 = 1e9+7;
//const int base=67;
int  n, m, s1, s2, s4, s3, sf, k, s5, s6, mx, s7, s8, s9, mx2, res, dem2 = 0, dem = 0, s33, dem3, dem4, mid, l2, r2, center;
int  i, s10, s12,k1,k2,k3,s11,lim,w,l,r,dem5,dem6,dem7,dem9,now,root,q,start,en;
int kk;
int el = 19;/*
main()
{
    ///top1tst
    if(fopen(task2".inp","r"))
    {
        fin(task2);
        fou(task2);
    }
    ///top1tst
    if(fopen(task".inp","r"))
    {
        fin(task);
        fou(task);
    }
    ///top1tst
    ios_base::sync_with_stdio(0);
    cout.tie(0);
    cin.tie(0);
//   cin>>s1;
    // int t;cin>>t;while(t--)
    phongbeo(),down
    checktime
    ///top1tst
}
#define NMAX  1400
#define DMAX  1400
#define QMAX  45000

static int T,N,M,Asktotal,Answertotal;
static int edge_list[NMAX][DMAX];
static int checked[NMAX][DMAX];
static int degree[NMAX];
static int visited[NMAX];
static void WA(int wa_num)
{
    printf("Wrong Answer[%d]\n",wa_num);
    exit(0);
}
void Detect(int T, int N);

void Answer(int A, int B)
{
    int i;
    if(A < 0||A >= B||B >= N) WA(1);
    for(i = 0 ; i < degree[A] ; i++)
    {
        if(edge_list[A][i] == B)
        {
            if(checked[A][i] == 1) WA(3);
            Answertotal++;
            checked[A][i] = 1;
            return;
        }
    }
    WA(2);
}
static void dfs(int now, int Place[])
{
    visited[now] = 1;
    int i;
    for(i = 0 ; i < degree[now] ; i++)
    {
        if(visited[edge_list[now][i]] == 0 && Place[edge_list[now][i]] == 1) dfs(edge_list[now][i], Place);
    }
}
int Ask(int A, int B, int Place[])
{
    int i;
    // cerr<<A<<" "<<B<<" "<<Place[A]<<" "<<Place[B]<<'\n';
    Asktotal++;
    if(Asktotal>QMAX) WA(5);
    if(A < 0||A >= B||B >= N) WA(4);
    if(Place[A] != 1) WA(4);
    if(Place[B] != 1) WA(4);
    for(i = 0 ; i < N ; i++)
    {
        if(Place[i]<0||Place[i]>1) WA(4);
        visited[i] = 0;
    }
    dfs(A, Place);
    return visited[B];
}*/
bool kkk=0;
vector<int> v[1401],ask,d[1401];
int vis[1401];
bool f[1401];
int tak[1401];
bool cf[1401][1401];
int par[1401];
bool dbcc[1401];
int nouse[1401];
bool check[1401][1401];
void dfs(int x,int y,int cc,int last)
{
    vis[x]=1;
    for(auto f:v[x])
        if(f^last)
        {
            dfs(f,y,cc,x);
        }
    ///if(kkk) cout<<x<<" "<<y<<" "<<cc<<" "<<vis[cc],down
    if(vis[cc]==1&&x!=y&&x!=cc&&!nouse[x])
        ask.pb(x);
    vis[x]=2;
}
void build(int x,int y)
{
    ask.clear();
    for(int i=0; i<n; i++)
        vis[i]=0;
    dfs(0,y,x,0);
}
bool are_connect(int x,int y)
{
    if(check[x][y])return 0;
    check[x][y]=1;
    check[y][x]=1;
    for(int i=0; i<n; i++)
    {
        if(i==x||i==y)tak[i]=1;
        else tak[i]=0;
    }
    return Ask(min(x,y),max(y,x),tak);
}
void add(int x,int y)
{
    if(f[y])return;
    if(are_connect(x,y))
    {
        f[y]=1;
        v[x].pb(y);
        v[y].pb(x);
        par[y]=x;
        cerr<<x<<" "<<y<<'\n';
        cf[x][y]=cf[y][x]=1;
        return;
    }
    build(x,y);
    for(int i=0; i<n; i++)
        if(nouse[i]==0)
            tak[i]=1;
        else tak[i]=0;
    for(auto x:ask)
        tak[x]=0;
    vector<int>rollback;
    if(Ask(min(x,y),max(y,x),tak)||ask.size()==0)
    {
        memset(vis,0,sizeof vis);
        for(auto x:ask) nouse[x]++,rollback.pb(x),vis[x]=1;
        ask.clear();
        for(int i=0; i<n; i++)
            if(!vis[i]&&!nouse[i]&&i!=x&&i!=y)ask.pb(i);
    }
    if(ask.size()==0)
    {
        debug
        exit(0);
    }
    l=0;
    r=ask.size()-2;
    while(l<=r)
    {
        int mid=l+r>>1;
        for(int i=0; i<n; i++)
            if(!nouse[i])
                tak[i]=1;
            else tak[i]=0;
        for(int i=0; i<=mid; i++)
            tak[ask[i]]=0;
        if(Ask(min(x,y),max(x,y),tak))l=mid+1;
        else r=mid-1;
    }
    for(int i=0; i<=r; i++)
        nouse[ask[i]]++,rollback.pb(ask[i]);
    int mid=ask[r+1];
    nouse[y]++;
    add(x,mid);
    nouse[y]--;
    nouse[x]++;
    add(mid,y);
    nouse[x]--;
    for(auto x:rollback)
        nouse[x]--;
}
void dfs2(int x,int y,int cc)
{
    vis[x]=1;
    for(auto f:v[x])
        if(f^y)
            dfs2(f,x,cc);
    if(vis[cc]==1)nouse[x]=1;
    vis[x]=2;
}
void work(int root,int x)
{
    if(are_connect(root,x)||cf[root][x])
    {
        if(!cf[root][x])
        {
            d[x].pb(root);
            d[root].pb(x);
        }
        cf[root][x]=1;
        cf[x][root]=1;
        for(auto f:v[root])
            if(f!=par[root]&&f!=x)
                work(f,x);
        return;
    }
    build(root,x);
    for(int i=0; i<n; i++)
        tak[i]=0;
    for(auto x:ask)
        tak[x]=1;
    tak[root]=1;
    tak[x]=1;
    while(Ask(min(root,x),max(root,x),tak))
    {
        l=0;
        r=ask.size()-1;
        reverse(ask.begin(),ask.end());
        while(l<=r)
        {
            int mid=l+r>>1;
            for(int i=0; i<n; i++)
                tak[i]=0;
            for(int i=0; i<=mid; i++)
                tak[ask[i]]=1;
            tak[root]=1;
            tak[x]=1;
            if(Ask(min(x,root),max(x,root),tak))r=mid-1;
            else l=mid+1;
        }
        int mid=ask[r+1];
        work(mid,x);
        memset(vis,0,sizeof vis);
        dfs2(0,0,mid);
        build(root,x);
        for(int i=0; i<n; i++)
            tak[i]=0;
        for(auto x:ask)
            tak[x]=1;
        tak[root]=1;
        tak[x]=1;
    }
}
void Detect(int T,int N)
{
    n=N;
    n=N;
    for(int i=1; i<n; i++)
    {
        add(0,i);
        memset(nouse,0,sizeof nouse);
    }
    for(int i=1; i<n; i++)
    {
        work(0,i);
        memset(nouse,0,sizeof nouse);
    }
    for(int i=0; i<n; i++)
    {
        for(auto x:v[i])
            if(x<i)
                Answer(x,i );
        for(auto x:d[i])
            if(x<i)
                Answer(x,i );
    }
}/*
void phongbeo()
{
    int i;
    scanf("%d%d%d",&T,&N,&M);
    Answertotal = 0;
    for(i = 0 ; i < N ; i++) degree[i] = 0;
    for(i = 0 ; i < M ; i++)
    {
        int ea,eb;
        scanf("%d%d",&ea,&eb);
        //ea=i;
        //eb=i+1;
        checked[ea][degree[ea]] =  0;
        checked[eb][degree[eb]] =  0;
        edge_list[ea][degree[ea]++] = eb;
        edge_list[eb][degree[eb]++] = ea;
    }
    Detect(T, N);
    if(Answertotal<M) WA(6);
    //printf("Accepted\n");
}
/**
1
6 8
1 3
4 2
2 5
2 0
3 0
1 5
3 5
2 1

*/

Compilation message (stderr)

park.cpp:26:15: warning: overflow in conversion from 'double' to 'int' changes value from '1.0e+17' to '2147483647' [-Woverflow]
   26 | const int inf=1e17;
      |               ^~~~

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 27 / 27
• Subtask 4: 30 / 30
• Subtask 5: 23 / 23