oj.uz

Submission #1119245

# Submission time Handle Problem Language Result Execution time Memory
1119245 2024-11-26T17:34:44 Z modwwe Board Game (JOI24_boardgame) C++17
54 / 100
 1599 ms 22868 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) continue;
        if(cc[x.b][x.c-vis[x.b]]) continue;
        if(x.c-vis[x.b]>=300)
        {
            cout<<-100;
            exit(0);
        }
        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 32 ms 14556 KB Output is correct
3 Correct 67 ms 22868 KB Output is correct
4 Correct 714 ms 19984 KB Output is correct

Subtask #2
0.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 3168 KB Output is correct
2 Correct 30 ms 14316 KB Output is correct
3 Incorrect 1599 ms 20768 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 3152 KB Output is correct
2 Correct 42 ms 14528 KB Output is correct
3 Correct 659 ms 22452 KB Output is correct
4 Correct 102 ms 21908 KB Output is correct
5 Correct 69 ms 22472 KB Output is correct
6 Correct 94 ms 20568 KB Output is correct
7 Incorrect 275 ms 20656 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 2896 KB Output is correct
2 Correct 8 ms 3152 KB Output is correct
3 Correct 6 ms 3152 KB Output is correct
4 Correct 23 ms 3604 KB Output is correct
5 Correct 12 ms 2700 KB Output is correct
6 Correct 8 ms 2692 KB Output is correct
7 Correct 6 ms 2900 KB Output is correct
8 Correct 5 ms 3156 KB Output is correct
9 Correct 6 ms 2900 KB Output is correct
10 Correct 5 ms 2900 KB Output is correct
11 Correct 5 ms 2900 KB Output is correct
12 Correct 5 ms 2900 KB Output is correct
13 Correct 7 ms 2900 KB Output is correct
14 Correct 4 ms 3156 KB Output is correct
15 Correct 22 ms 3164 KB Output is correct
16 Correct 34 ms 3156 KB Output is correct
17 Correct 96 ms 3156 KB Output is correct
18 Correct 5 ms 3156 KB Output is correct
19 Correct 5 ms 3156 KB Output is correct
20 Correct 29 ms 3184 KB Output is correct
21 Correct 6 ms 3156 KB Output is correct

Subtask #5
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 20552 KB Output is correct
2 Correct 52 ms 21048 KB Output is correct
3 Correct 41 ms 20560 KB Output is correct
4 Correct 66 ms 20944 KB Output is correct
5 Correct 71 ms 20652 KB Output is correct
6 Correct 41 ms 17224 KB Output is correct
7 Correct 43 ms 11768 KB Output is correct
8 Correct 21 ms 10832 KB Output is correct
9 Correct 22 ms 11088 KB Output is correct
10 Correct 39 ms 17224 KB Output is correct
11 Correct 42 ms 17284 KB Output is correct
12 Correct 48 ms 19784 KB Output is correct

Subtask #6
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 20552 KB Output is correct
2 Correct 52 ms 21048 KB Output is correct
3 Correct 41 ms 20560 KB Output is correct
4 Correct 66 ms 20944 KB Output is correct
5 Correct 71 ms 20652 KB Output is correct
6 Correct 41 ms 17224 KB Output is correct
7 Correct 43 ms 11768 KB Output is correct
8 Correct 21 ms 10832 KB Output is correct
9 Correct 22 ms 11088 KB Output is correct
10 Correct 39 ms 17224 KB Output is correct
11 Correct 42 ms 17284 KB Output is correct
12 Correct 48 ms 19784 KB Output is correct
13 Correct 129 ms 20604 KB Output is correct
14 Correct 250 ms 21880 KB Output is correct
15 Correct 1026 ms 22344 KB Output is correct
16 Correct 882 ms 20304 KB Output is correct
17 Correct 813 ms 18908 KB Output is correct
18 Correct 777 ms 19252 KB Output is correct
19 Correct 1380 ms 20188 KB Output is correct
20 Correct 690 ms 21020 KB Output is correct
21 Correct 28 ms 11568 KB Output is correct
22 Correct 191 ms 12900 KB Output is correct
23 Correct 375 ms 12908 KB Output is correct
24 Correct 50 ms 18408 KB Output is correct
25 Correct 320 ms 20040 KB Output is correct
26 Correct 643 ms 19652 KB Output is correct
27 Correct 40 ms 13112 KB Output is correct
28 Correct 209 ms 12920 KB Output is correct
29 Correct 511 ms 12964 KB Output is correct
30 Correct 59 ms 19724 KB Output is correct
31 Correct 400 ms 20352 KB Output is correct
32 Correct 819 ms 19700 KB Output is correct

Subtask #7
0.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 2896 KB Output is correct
2 Correct 8 ms 3152 KB Output is correct
3 Correct 6 ms 3152 KB Output is correct
4 Correct 23 ms 3604 KB Output is correct
5 Correct 12 ms 2700 KB Output is correct
6 Correct 8 ms 2692 KB Output is correct
7 Correct 6 ms 2900 KB Output is correct
8 Correct 5 ms 3156 KB Output is correct
9 Correct 6 ms 2900 KB Output is correct
10 Correct 5 ms 2900 KB Output is correct
11 Correct 5 ms 2900 KB Output is correct
12 Correct 5 ms 2900 KB Output is correct
13 Correct 7 ms 2900 KB Output is correct
14 Correct 4 ms 3156 KB Output is correct
15 Correct 22 ms 3164 KB Output is correct
16 Correct 34 ms 3156 KB Output is correct
17 Correct 96 ms 3156 KB Output is correct
18 Correct 5 ms 3156 KB Output is correct
19 Correct 5 ms 3156 KB Output is correct
20 Correct 29 ms 3184 KB Output is correct
21 Correct 6 ms 3156 KB Output is correct
22 Correct 95 ms 13480 KB Output is correct
23 Correct 190 ms 15156 KB Output is correct
24 Correct 67 ms 13348 KB Output is correct
25 Correct 1340 ms 13380 KB Output is correct
26 Correct 128 ms 14028 KB Output is correct
27 Correct 45 ms 14204 KB Output is correct
28 Correct 109 ms 13932 KB Output is correct
29 Correct 40 ms 14288 KB Output is correct
30 Correct 56 ms 13396 KB Output is correct
31 Correct 34 ms 14224 KB Output is correct
32 Incorrect 1075 ms 9848 KB Output isn't correct
33 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 32 ms 14556 KB Output is correct
3 Correct 67 ms 22868 KB Output is correct
4 Correct 714 ms 19984 KB Output is correct
5 Correct 6 ms 3168 KB Output is correct
6 Correct 30 ms 14316 KB Output is correct
7 Incorrect 1599 ms 20768 KB Output isn't correct
8 Halted 0 ms 0 KB -