제출 #1159321

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1159321		modwwe	한자 끝말잇기 (JOI14_kanji)	C++20	0 / 100	120 ms	5732 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 ll 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];
ll c[10000];
int a[10000];
int b[10000];
int s[10000];
int t[10000];
int u[10000];
int trace[500][500];
bool choose[10000];
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,trace[i][j]=-1;
        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++)
            {
                ///if(i==0&&j==1) cout<<dp[i][j],down
                if(mid==i||mid==j) continue;
                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;
            }
}
ll 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]];
}
ll 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++;
            }
            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 ll 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];
ll 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,trace[i][j]=-1;
        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++)
            {
                if(mid==i||mid==j) continue;
                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;
            }
}
ll 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]];
}
ll 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]==-1)
    {
        //cout<<cc[x][y],down
        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);
    }
}

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