Submission #1159249

#	Time	Username	Problem	Language	Result	Execution time	Memory
1159249		modwwe	한자 끝말잇기 (JOI14_kanji)	C++20	0 / 100	206 ms	327680 KiB

Anna

#include "Annalib.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 "ftree"
#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 = 3e18+1;
const ll mod2 = 1e9+7;
//const ll 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;
int kk;
int el = 19;
ll dp[500][500];
int c[10000];
int a[10000];
int b[10000];
int s[10000];
int t[10000];
int u[10000];
int trace[500][500];
bool choose[500];
vector<int> g[500];
vector<pair<int,int>>send;
void rebuild()
{
    for(int i=0; i<n; i++)
    {
        for(int j=0; j<n; j++)
            dp[i][j]=inf;
        dp[i][i]=0;
    }
    for(int i=1; i<=m; i++)
        if(!choose[i])
            dp[a[i]][b[i]]=c[i];
    for(int mid=0; mid<n; mid++)
        for(int i=0; i<n; i++)
            for(int j=0; j<n; j++)
            {
                dp[i][j]=min(dp[i][j],dp[i][mid]+dp[mid][j]);
                if(dp[i][j]==dp[i][mid]+dp[mid][j])
                    trace[i][j]=mid;
            }
}
int cost(int u,int y)
{
    if(y==0)return dp[s[u]][t[u]];
    return dp[s[u]][a[y]]+dp[b[y]][t[u]];
}
int f(int x,int y,int z)
{
    return cost(x,y)-cost(x,z);
}
bool cmp(int x,int y)
{
    return f(x,root,now)<f(y,root,now);
}
void Anna(int N, int M, int A[], int B[], long long C[], int Q, int S[], int T[], int K, int U[])
{
    n=N;
    m=M;
    k=K;
    q=Q;
    for(int i=1; i<=k; i++)
        u[i]=U[i-1]+1;
    for(int i=1; i<=q; i++)
        s[i]=S[i-1],t[i]=T[i-1];
    for(int i=1; i<=m; i++)
        a[i]=A[i-1],b[i]=B[i-1],c[i]=C[i-1];
    for(int i=1; i<=k; i++)
        choose[u[i]]=1;
    rebuild();
    for(int i=1; i<=q; i++)
        g[0].pb(i);
    for(int i=1; i<=k; i++)
        for(int j=0; j<i; j++)
        {
            root=u[i];
            now=u[j];
            sort(g[j].begin(),g[j].end(),cmp);
            int pos=0;
            while(true)
            {
                if(pos==g[j].size())break;
                if(cost(g[j][pos],root)+c[root]>=cost(g[j][pos],now)+c[now]) break;
                g[i].pb(g[j][pos]);
                pos++;
            }
            for(int ff=0; ff<pos; ff++)
                g[i].pb(g[j][ff]);
            send.pb({pos,g[j].size()+1});
            reverse(g[j].begin(),g[j].end());
            while(pos!=0)
            {
                g[j].pop_back();
                pos--;
            }
        }
    long long total=0;
    reverse(send.begin(),send.end());
    for(auto x:send)
        total=total*x.second+x.first;
    while(total!=0)Tap(total&1),total/=2;
}

Bruno

#include "Brunolib.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 "ftree"
#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 =3e18+1;
const ll mod2 = 1e9+7;
//const ll 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;
int kk;
int el = 19;
long long dp[500][500];
int c[10000];
int a[10000];
int b[10000];
int s[10000];
int t[10000];
int u[10000];
int trace[500][500];
bool choose[10000];
int cc[500][500];
vector<int> g[500],v,result[500];
void rebuild()
{
    for(int i=0; i<n; i++)
    {
        for(int j=0; j<n; j++)
            dp[i][j]=inf;
        dp[i][i]=0;
    }
    for(int i=1; i<=m; i++)
        if(!choose[i])
            dp[a[i]][b[i]]=c[i];
    for(int mid=0; mid<n; mid++)
        for(int i=0; i<n; i++)
            for(int j=0; j<n; j++)
            {
                dp[i][j]=min(dp[i][j],dp[i][mid]+dp[mid][j]);
                if(dp[i][j]==dp[i][mid]+dp[mid][j])
                    trace[i][j]=mid;
            }
}
int cost(int u,int y)
{
    if(y==0)return dp[s[u]][t[u]];
    return dp[s[u]][a[y]]+dp[b[y]][t[u]];
}
int f(int x,int y,int z)
{
    return cost(x,y)-cost(x,z);
}
bool cmp(int x,int y)
{
    return f(x,root,now)<f(y,root,now);
}
void dnc(int x,int y)
{
    if(x==y) return;
    if(dp[x][y]==inf) assert(0);
    if(trace[x][y]==x||trace[x][y]==y)
    {
        v.pb(cc[x][y]);
        return;
    }
    dnc(x,trace[x][y]);
    dnc(trace[x][y],y);
}

void Bruno(int N, int M, int A[], int B[], long long C[], int Q, int S[], int T[], int K, int U[], int L, int X[])
{
    long long total=0;
    n=N;
    m=M;
    k=K;
    q=Q;
    for(int i=0; i<L; i++)
        total=total+mask(i)*X[i];
    for(int i=1; i<=k; i++)
        u[i]=U[i-1]+1;
    for(int i=1; i<=q; i++)
        s[i]=S[i-1],t[i]=T[i-1];
    for(int i=1; i<=m; i++)
        a[i]=A[i-1],b[i]=B[i-1],c[i]=C[i-1],cc[a[i]][b[i]]=i-1;
    for(int i=1; i<=k; i++)
        choose[u[i]]=1;
    rebuild();
    for(int i=1; i<=q; i++)
        g[0].pb(i);
    for(int i=1; i<=k; i++)
        for(int j=0; j<i; j++)
        {
            root=u[i];
            now=u[j];
            sort(g[j].begin(),g[j].end(),cmp);
            int pos=total%(g[j].size()+1);
            total/=(g[j].size()+1);
            for(int ff=0; ff<pos; ff++)
                g[i].pb(g[j][ff]);
            reverse(g[j].begin(),g[j].end());
            while(pos!=0)
            {
                g[j].pop_back();
                pos--;
            }
        }
    for(int i=0; i<=k; i++)
    {
        for(auto x:g[i])
        {
            if(i==0)dnc(s[x],t[x]);
            else dnc(s[x],a[u[i]]),v.pb(u[i]-1),dnc(b[u[i]],t[x]);
            result[x]=v;

          v.clear();
        }
    }
    for(int i=1;i<=q;i++)
    {
        result[i].pb(-1);
        for(auto x:result[i])
            Answer(x);
    }
}

Compilation message (stderr)

# 1번째 컴파일 단계

Anna.cpp:26:21: warning: overflow in conversion from 'double' to 'int' changes value from '3.0e+18' to '2147483647' [-Woverflow]
   26 | const int inf = 3e18+1;
      |                 ~~~~^~

# 2번째 컴파일 단계

Bruno.cpp:26:20: warning: overflow in conversion from 'double' to 'int' changes value from '3.0e+18' to '2147483647' [-Woverflow]
   26 | const int inf =3e18+1;
      |                ~~~~^~

• Subtask 1: 0 / 10
• Subtask 2: 0 / 22
• Subtask 3: 0 / 8
• Subtask 4: 0 / 40
• Subtask 5: 0 / 20