oj.uz

Submission #1119250

# Submission time Handle Problem Language Result Execution time Memory
1119250 2024-11-26T17:36:47 Z modwwe Board Game (JOI24_boardgame) C++17
35 / 100
 1469 ms 22724 KB 
#pragma GCC optimize("Ofast,unroll-loops")
//#pragma GCC optimize("conserve-stack")
#include<bits/stdc++.h>
#define int  long long
#define ll long long
#define down cout<<'\n';
#define debug cout<<" cucuucucuuu",down
#define NHP     ios_base::sync_with_stdio(0);cout.tie(0);cin.tie(0);
#define modwwe  int t;cin>>t; while(t--)
#define bit(i,j) (i>>j&1)
#define sobit(a) __builtin_popcountll(a)
#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) (1<<k)
#define mp make_pair
#define checktime   cerr << (double)clock() / CLOCKS_PER_SEC * 1000  << " ms";
using namespace std;
#define getchar_unlocked getchar

inline int scan()
{
    char c = getchar_unlocked();
    int x = 0;
    while (c < '0' || c > '9')
    {
        c = getchar_unlocked();
    }
    while (c >= '0' && c <= '9')
    {
        x = (x << 1) + (x << 3) + c - '0';
        c = getchar_unlocked();
    }
    return x;
}
void phongbeo();
const int inf = 1e18;
const ll mod2 = 1e9 + 7;
const int  mod1 = 998244353;
const ll base=67;
int add(int x,int y)
{
    if(x+y>=mod2) x-=mod2;
    if(x+y<0)x+=mod2;
    return x+y;
}
struct icd
{
    long double a;
    int b;
};
struct ib
{
    int a;
    int b;
};
struct ic
{
    int a, b, c;
};
struct id
{
    int a, b, c, d;
};
struct ie
{
    int a, b, c, d, e;

};
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,t,lim,w,l,r ;
int kk;
int el = 19;
main()
{
    if(fopen(task".inp","r"))
    {
        fin(task);
        fou(task);
    }
    NHP
    /// cin>>s1;
    // modwwe
    phongbeo();
    // checktime
}
string s;
vector<int> v[50001];
int ans[50001];
int c[50001];
int d[50001];
int cost[50001];
int vis[50001];
int a[50001];
vector<int> cd;
struct cmp
{
    bool operator()(id a,id b)
    {
        return a.a>b.a;
    }
};
void bfs(int c[],bool k)
{
    deque<ib>q;
    for(int i=1; i<=n; i++)
        if(s[i-1]=='1')
        {
            if(k)
            {
                for(auto f:v[i])
                    if(s[f-1]=='1')
                    {
                        q.pb({0,i});
                    }
            }
            else
            {
                q.pb({0,i});
            }
        }
    while(!q.empty())
    {
        ib x=q.front();
        q.pop_front();
        if(vis[x.b]) continue;
        vis[x.b]=1;
        for(auto f:v[x.b])
        {
            c[f]=min(x.a+1,c[f]);
            if(s[f-1]=='1')q.push_front({x.a,f});
            else q.push_back({x.a+1,f});
        }
    }
}
bool cc[50001][301];

namespace k_low
{
priority_queue<id,vector<id>,cmp>p;
void solve()
{
    sort(cd.begin(),cd.end());
    int total=0;
    for(int i=0; i<k; i++)
    {
        p.push({total+s4,s9,i,0});
        cost[i]=i+(k-i-1)*2;
        total+=cd[i];
    }
    while(!p.empty())
    {
        id x=p.top();
        p.pop();
        if(cc[x.b][x.c]) continue;
        cc[x.b][x.c]=1;
        if(x.d)
        {
            ans[x.b]=min(ans[x.b],x.a);
        }
        for(auto f:v[x.b])
            if(s[f-1]=='1')
            {
                if(x.d)
                    ans[f]=min(ans[f],x.a+1);
                p.push({x.a+cost[x.c]+1,f,x.c,1});
            }
            else
            {
                p.push({x.a+1,f,x.c,x.d});
            }
    }
     p.push({0,s9,0,0});
    ans[s9]=0;
    while(!p.empty())
    {
        id x=p.top();
        p.pop();
        if(vis[x.b]) continue;
        vis[x.b]=1;
        for(auto f:v[x.b])
        {
            ans[f]=min(ans[f],x.a+1);
            if(s[f-1]=='0') p.push({x.a+1,f,x.c,x.d});
        }
    }
}
};
namespace k_high
{
int pre[50001];
int cur[50001];
void solve()
{
    for(int i=2; i<=k; i++)
    {
        l=a[i];
        int ci=c[l];
        int di=d[l];
        if(c[l]==0) c[l]+=2;
        if(d[l]==0) d[l]=1;
          c[l]-=2;
        d[l]--;
        if(d[l]+1==inf){
   pre[1]+=c[l];
   cur[1]+=2;
        }
        else{
        s3=d[l]-c[l];
        pre[s3]+=d[l];
        pre[s3]-=c[l];
        pre[1]+=c[l];
        cur[s3]++;
        cur[s3]-=2;
        cur[1]+=2;
        pre[s3]-=(s3-1);
        }
        c[l]=ci;
        d[l]=di;

    }
    for(int i=1; i<=n; i++)
        cur[i]+=cur[i-1],
                pre[i]+=pre[i-1]+cur[i];
    deque<ic> q;
    q.push_front({0,s9});
    memset(vis,-1,sizeof vis);
    while(!q.empty())
    {
        ic x=q.front();
        q.pop_front();
        if(vis[x.b]!=-1) continue;
        vis[x.b]=x.a;
        for(auto f:v[x.b])
            if(s[f-1]=='1') q.pb({x.a+1,f});
            else q.push_front({x.a,f});
    }

    q.pb({0,s9,0});
    while(!q.empty())
    {
        ic x=q.front();
        q.pop_front();
        if((x.c-vis[x.b])*(k-1)>=n&&x.c>n+1) continue;
        if(cc[x.b][x.c-vis[x.b]]) continue;
        cc[x.b][x.c-vis[x.b]]=1;
        if(s[x.b-1]=='1')s4=1;
        else s4=0;
        ans[x.b]=min(ans[x.b],x.a+pre[x.c-s4]);
        for(auto f:v[x.b])
            if(s[f-1]=='1')q.pb({x.a+1,f,x.c+1});
            else q.pb({x.a+1,f,x.c});
    }
    memset(vis,0,sizeof vis);
}
};
void phongbeo()
{
    cin>>n>>m>>k;
    for(int i=1; i<=m; i++)
        cin>>l>>r,v[l].pb(r),v[r].pb(l);
    cin>>s;
    for(int i=1; i<=n; i++)
        d[i]=inf,c[i]=inf;
    bfs(c,0);
    memset(vis,0,sizeof vis);
    bfs(d,1);
    memset(vis,0,sizeof vis);
    for(int i=1; i<=k; i++)
    {
        cin>>l;
        int ci=c[l];
        int di=d[l];
        if(c[l]==0) c[l]+=2;
        if(d[l]==0) d[l]=1;
        if(i==1)s9=l;
        else c[l]-=2,d[l]--,cd.pb(d[l]-c[l]),s4+=c[l];
        a[i]=l;
        c[l]=ci;
        d[l]=di;
    }
    for(int i=1; i<=n; i++)
        ans[i]=inf;
    if(k<=250)k_low::solve();
    else k_high::solve();
    for(int i=1; i<=n; i++)
        cout<<ans[i]<<" ";
}

Compilation message

Main.cpp:75:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   75 | main()
      | ^~~~
Main.cpp: In function 'int main()':
Main.cpp:13:23: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   13 | #define fin(x) freopen(x".inp","r",stdin)
      |                ~~~~~~~^~~~~~~~~~~~~~~~~~~
Main.cpp:79:9: note: in expansion of macro 'fin'
   79 |         fin(task);
      |         ^~~
Main.cpp:14:23: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   14 | #define fou(x) freopen(x".out","w",stdout)
      |                ~~~~~~~^~~~~~~~~~~~~~~~~~~~
Main.cpp:80:9: note: in expansion of macro 'fou'
   80 |         fou(task);
      |         ^~~

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 3152 KB Output is correct
2 Correct 24 ms 14596 KB Output is correct
3 Correct 45 ms 22724 KB Output is correct
4 Correct 583 ms 20504 KB Output is correct

Subtask #2
0.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 3152 KB Output is correct
2 Correct 686 ms 14944 KB Output is correct
3 Incorrect 1469 ms 20764 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0.0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 39 ms 3152 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 2696 KB Output is correct
2 Correct 8 ms 3232 KB Output is correct
3 Correct 50 ms 3252 KB Output is correct
4 Correct 26 ms 3408 KB Output is correct
5 Correct 12 ms 2640 KB Output is correct
6 Correct 6 ms 2640 KB Output is correct
7 Correct 37 ms 2896 KB Output is correct
8 Correct 48 ms 3312 KB Output is correct
9 Correct 5 ms 2896 KB Output is correct
10 Correct 4 ms 2896 KB Output is correct
11 Correct 5 ms 2896 KB Output is correct
12 Correct 6 ms 2896 KB Output is correct
13 Correct 9 ms 3152 KB Output is correct
14 Correct 6 ms 3152 KB Output is correct
15 Correct 17 ms 3152 KB Output is correct
16 Correct 40 ms 3168 KB Output is correct
17 Correct 113 ms 3164 KB Output is correct
18 Correct 5 ms 2896 KB Output is correct
19 Correct 5 ms 2896 KB Output is correct
20 Correct 41 ms 3144 KB Output is correct
21 Incorrect 26 ms 3280 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #5
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 68 ms 20044 KB Output is correct
2 Correct 58 ms 20280 KB Output is correct
3 Correct 57 ms 20416 KB Output is correct
4 Correct 75 ms 20292 KB Output is correct
5 Correct 79 ms 20276 KB Output is correct
6 Correct 42 ms 16712 KB Output is correct
7 Correct 39 ms 11768 KB Output is correct
8 Correct 26 ms 10804 KB Output is correct
9 Correct 28 ms 10832 KB Output is correct
10 Correct 42 ms 17224 KB Output is correct
11 Correct 48 ms 16760 KB Output is correct
12 Correct 54 ms 19748 KB Output is correct

Subtask #6
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 68 ms 20044 KB Output is correct
2 Correct 58 ms 20280 KB Output is correct
3 Correct 57 ms 20416 KB Output is correct
4 Correct 75 ms 20292 KB Output is correct
5 Correct 79 ms 20276 KB Output is correct
6 Correct 42 ms 16712 KB Output is correct
7 Correct 39 ms 11768 KB Output is correct
8 Correct 26 ms 10804 KB Output is correct
9 Correct 28 ms 10832 KB Output is correct
10 Correct 42 ms 17224 KB Output is correct
11 Correct 48 ms 16760 KB Output is correct
12 Correct 54 ms 19748 KB Output is correct
13 Correct 151 ms 20632 KB Output is correct
14 Correct 272 ms 21292 KB Output is correct
15 Correct 941 ms 21636 KB Output is correct
16 Correct 826 ms 20436 KB Output is correct
17 Correct 799 ms 18316 KB Output is correct
18 Correct 868 ms 18876 KB Output is correct
19 Correct 922 ms 19672 KB Output is correct
20 Correct 564 ms 20520 KB Output is correct
21 Correct 30 ms 11088 KB Output is correct
22 Correct 193 ms 12756 KB Output is correct
23 Correct 323 ms 12520 KB Output is correct
24 Correct 56 ms 17752 KB Output is correct
25 Correct 293 ms 19924 KB Output is correct
26 Correct 620 ms 19768 KB Output is correct
27 Correct 33 ms 12624 KB Output is correct
28 Correct 184 ms 12608 KB Output is correct
29 Correct 422 ms 12612 KB Output is correct
30 Correct 56 ms 19716 KB Output is correct
31 Correct 347 ms 19784 KB Output is correct
32 Correct 746 ms 19888 KB Output is correct

Subtask #7
0.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 2696 KB Output is correct
2 Correct 8 ms 3232 KB Output is correct
3 Correct 50 ms 3252 KB Output is correct
4 Correct 26 ms 3408 KB Output is correct
5 Correct 12 ms 2640 KB Output is correct
6 Correct 6 ms 2640 KB Output is correct
7 Correct 37 ms 2896 KB Output is correct
8 Correct 48 ms 3312 KB Output is correct
9 Correct 5 ms 2896 KB Output is correct
10 Correct 4 ms 2896 KB Output is correct
11 Correct 5 ms 2896 KB Output is correct
12 Correct 6 ms 2896 KB Output is correct
13 Correct 9 ms 3152 KB Output is correct
14 Correct 6 ms 3152 KB Output is correct
15 Correct 17 ms 3152 KB Output is correct
16 Correct 40 ms 3168 KB Output is correct
17 Correct 113 ms 3164 KB Output is correct
18 Correct 5 ms 2896 KB Output is correct
19 Correct 5 ms 2896 KB Output is correct
20 Correct 41 ms 3144 KB Output is correct
21 Incorrect 26 ms 3280 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #8
0.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 3152 KB Output is correct
2 Correct 24 ms 14596 KB Output is correct
3 Correct 45 ms 22724 KB Output is correct
4 Correct 583 ms 20504 KB Output is correct
5 Correct 44 ms 3152 KB Output is correct
6 Correct 686 ms 14944 KB Output is correct
7 Incorrect 1469 ms 20764 KB Output isn't correct
8 Halted 0 ms 0 KB -