oj.uz

Submission #1119264

# Submission time Handle Problem Language Result Execution time Memory
1119264 2024-11-26T17:49:02 Z modwwe Board Game (JOI24_boardgame) C++17
100 / 100
 2499 ms 58252 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 = 1e10;
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][1001];

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});
            }
    }
    deque<ib> q;
    q.pb({0,s9});
    ans[s9]=0;
    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])
        {
            ans[f]=min(ans[f],x.a+1);
            if(s[f-1]=='0') q.pb({x.a+1,f});
        }
    }
}
};
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();
        s8=max(s8,x.c);
        if((x.c-vis[x.b])*(k-1)>=n||x.c>n) 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<=70)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 7 ms 5364 KB Output is correct
2 Correct 44 ms 35100 KB Output is correct
3 Correct 77 ms 56256 KB Output is correct
4 Correct 63 ms 55168 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 5200 KB Output is correct
2 Correct 47 ms 34248 KB Output is correct
3 Correct 1483 ms 55300 KB Output is correct
4 Correct 100 ms 54248 KB Output is correct
5 Correct 103 ms 55680 KB Output is correct
6 Correct 158 ms 54344 KB Output is correct
7 Correct 241 ms 44040 KB Output is correct
8 Correct 115 ms 51016 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 5200 KB Output is correct
2 Correct 50 ms 34192 KB Output is correct
3 Correct 665 ms 56048 KB Output is correct
4 Correct 139 ms 55540 KB Output is correct
5 Correct 83 ms 56008 KB Output is correct
6 Correct 127 ms 54376 KB Output is correct
7 Correct 324 ms 54916 KB Output is correct
8 Correct 99 ms 56512 KB Output is correct
9 Correct 41 ms 15392 KB Output is correct
10 Correct 51 ms 19016 KB Output is correct

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 3812 KB Output is correct
2 Correct 10 ms 5200 KB Output is correct
3 Correct 8 ms 5084 KB Output is correct
4 Correct 26 ms 5332 KB Output is correct
5 Correct 12 ms 4176 KB Output is correct
6 Correct 8 ms 4176 KB Output is correct
7 Correct 6 ms 3664 KB Output is correct
8 Correct 7 ms 5200 KB Output is correct
9 Correct 7 ms 4564 KB Output is correct
10 Correct 8 ms 4432 KB Output is correct
11 Correct 7 ms 4432 KB Output is correct
12 Correct 8 ms 4688 KB Output is correct
13 Correct 10 ms 4820 KB Output is correct
14 Correct 6 ms 4944 KB Output is correct
15 Correct 22 ms 5200 KB Output is correct
16 Correct 7 ms 5200 KB Output is correct
17 Correct 7 ms 5200 KB Output is correct
18 Correct 6 ms 4944 KB Output is correct
19 Correct 9 ms 5132 KB Output is correct
20 Correct 8 ms 5212 KB Output is correct
21 Correct 7 ms 5200 KB Output is correct

Subtask #5
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 88 ms 54220 KB Output is correct
2 Correct 89 ms 54584 KB Output is correct
3 Correct 72 ms 54856 KB Output is correct
4 Correct 99 ms 54424 KB Output is correct
5 Correct 96 ms 54220 KB Output is correct
6 Correct 59 ms 44644 KB Output is correct
7 Correct 48 ms 18380 KB Output is correct
8 Correct 35 ms 26184 KB Output is correct
9 Correct 42 ms 26192 KB Output is correct
10 Correct 81 ms 42812 KB Output is correct
11 Correct 71 ms 42824 KB Output is correct
12 Correct 75 ms 54104 KB Output is correct

Subtask #6
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 88 ms 54220 KB Output is correct
2 Correct 89 ms 54584 KB Output is correct
3 Correct 72 ms 54856 KB Output is correct
4 Correct 99 ms 54424 KB Output is correct
5 Correct 96 ms 54220 KB Output is correct
6 Correct 59 ms 44644 KB Output is correct
7 Correct 48 ms 18380 KB Output is correct
8 Correct 35 ms 26184 KB Output is correct
9 Correct 42 ms 26192 KB Output is correct
10 Correct 81 ms 42812 KB Output is correct
11 Correct 71 ms 42824 KB Output is correct
12 Correct 75 ms 54104 KB Output is correct
13 Correct 190 ms 54992 KB Output is correct
14 Correct 317 ms 55084 KB Output is correct
15 Correct 1152 ms 55860 KB Output is correct
16 Correct 2499 ms 55844 KB Output is correct
17 Correct 937 ms 45600 KB Output is correct
18 Correct 1018 ms 46232 KB Output is correct
19 Correct 2221 ms 42540 KB Output is correct
20 Correct 750 ms 54592 KB Output is correct
21 Correct 58 ms 27588 KB Output is correct
22 Correct 238 ms 33096 KB Output is correct
23 Correct 464 ms 34700 KB Output is correct
24 Correct 76 ms 46408 KB Output is correct
25 Correct 338 ms 53572 KB Output is correct
26 Correct 1380 ms 56504 KB Output is correct
27 Correct 47 ms 33104 KB Output is correct
28 Correct 184 ms 33096 KB Output is correct
29 Correct 275 ms 34380 KB Output is correct
30 Correct 90 ms 54048 KB Output is correct
31 Correct 397 ms 54600 KB Output is correct
32 Correct 1104 ms 55796 KB Output is correct

Subtask #7
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 3812 KB Output is correct
2 Correct 10 ms 5200 KB Output is correct
3 Correct 8 ms 5084 KB Output is correct
4 Correct 26 ms 5332 KB Output is correct
5 Correct 12 ms 4176 KB Output is correct
6 Correct 8 ms 4176 KB Output is correct
7 Correct 6 ms 3664 KB Output is correct
8 Correct 7 ms 5200 KB Output is correct
9 Correct 7 ms 4564 KB Output is correct
10 Correct 8 ms 4432 KB Output is correct
11 Correct 7 ms 4432 KB Output is correct
12 Correct 8 ms 4688 KB Output is correct
13 Correct 10 ms 4820 KB Output is correct
14 Correct 6 ms 4944 KB Output is correct
15 Correct 22 ms 5200 KB Output is correct
16 Correct 7 ms 5200 KB Output is correct
17 Correct 7 ms 5200 KB Output is correct
18 Correct 6 ms 4944 KB Output is correct
19 Correct 9 ms 5132 KB Output is correct
20 Correct 8 ms 5212 KB Output is correct
21 Correct 7 ms 5200 KB Output is correct
22 Correct 105 ms 33408 KB Output is correct
23 Correct 232 ms 35140 KB Output is correct
24 Correct 87 ms 33664 KB Output is correct
25 Correct 217 ms 33988 KB Output is correct
26 Correct 162 ms 34452 KB Output is correct
27 Correct 56 ms 34120 KB Output is correct
28 Correct 118 ms 34436 KB Output is correct
29 Correct 46 ms 34776 KB Output is correct
30 Correct 74 ms 33476 KB Output is correct
31 Correct 49 ms 34240 KB Output is correct
32 Correct 136 ms 23772 KB Output is correct
33 Correct 48 ms 24400 KB Output is correct
34 Correct 304 ms 34844 KB Output is correct
35 Correct 260 ms 34888 KB Output is correct
36 Correct 167 ms 34332 KB Output is correct
37 Correct 152 ms 33792 KB Output is correct
38 Correct 107 ms 33352 KB Output is correct
39 Correct 258 ms 33876 KB Output is correct
40 Correct 186 ms 35616 KB Output is correct
41 Correct 158 ms 35592 KB Output is correct
42 Correct 106 ms 35944 KB Output is correct
43 Correct 82 ms 35628 KB Output is correct
44 Correct 85 ms 34060 KB Output is correct
45 Correct 83 ms 35320 KB Output is correct
46 Correct 69 ms 33864 KB Output is correct
47 Correct 66 ms 34076 KB Output is correct
48 Correct 65 ms 33864 KB Output is correct
49 Correct 52 ms 34376 KB Output is correct
50 Correct 55 ms 34172 KB Output is correct
51 Correct 49 ms 33236 KB Output is correct
52 Correct 72 ms 33692 KB Output is correct
53 Correct 426 ms 33920 KB Output is correct
54 Correct 51 ms 35140 KB Output is correct

Subtask #8
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 5364 KB Output is correct
2 Correct 44 ms 35100 KB Output is correct
3 Correct 77 ms 56256 KB Output is correct
4 Correct 63 ms 55168 KB Output is correct
5 Correct 6 ms 5200 KB Output is correct
6 Correct 47 ms 34248 KB Output is correct
7 Correct 1483 ms 55300 KB Output is correct
8 Correct 100 ms 54248 KB Output is correct
9 Correct 103 ms 55680 KB Output is correct
10 Correct 158 ms 54344 KB Output is correct
11 Correct 241 ms 44040 KB Output is correct
12 Correct 115 ms 51016 KB Output is correct
13 Correct 7 ms 5200 KB Output is correct
14 Correct 50 ms 34192 KB Output is correct
15 Correct 665 ms 56048 KB Output is correct
16 Correct 139 ms 55540 KB Output is correct
17 Correct 83 ms 56008 KB Output is correct
18 Correct 127 ms 54376 KB Output is correct
19 Correct 324 ms 54916 KB Output is correct
20 Correct 99 ms 56512 KB Output is correct
21 Correct 41 ms 15392 KB Output is correct
22 Correct 51 ms 19016 KB Output is correct
23 Correct 5 ms 3812 KB Output is correct
24 Correct 10 ms 5200 KB Output is correct
25 Correct 8 ms 5084 KB Output is correct
26 Correct 26 ms 5332 KB Output is correct
27 Correct 12 ms 4176 KB Output is correct
28 Correct 8 ms 4176 KB Output is correct
29 Correct 6 ms 3664 KB Output is correct
30 Correct 7 ms 5200 KB Output is correct
31 Correct 7 ms 4564 KB Output is correct
32 Correct 8 ms 4432 KB Output is correct
33 Correct 7 ms 4432 KB Output is correct
34 Correct 8 ms 4688 KB Output is correct
35 Correct 10 ms 4820 KB Output is correct
36 Correct 6 ms 4944 KB Output is correct
37 Correct 22 ms 5200 KB Output is correct
38 Correct 7 ms 5200 KB Output is correct
39 Correct 7 ms 5200 KB Output is correct
40 Correct 6 ms 4944 KB Output is correct
41 Correct 9 ms 5132 KB Output is correct
42 Correct 8 ms 5212 KB Output is correct
43 Correct 7 ms 5200 KB Output is correct
44 Correct 88 ms 54220 KB Output is correct
45 Correct 89 ms 54584 KB Output is correct
46 Correct 72 ms 54856 KB Output is correct
47 Correct 99 ms 54424 KB Output is correct
48 Correct 96 ms 54220 KB Output is correct
49 Correct 59 ms 44644 KB Output is correct
50 Correct 48 ms 18380 KB Output is correct
51 Correct 35 ms 26184 KB Output is correct
52 Correct 42 ms 26192 KB Output is correct
53 Correct 81 ms 42812 KB Output is correct
54 Correct 71 ms 42824 KB Output is correct
55 Correct 75 ms 54104 KB Output is correct
56 Correct 190 ms 54992 KB Output is correct
57 Correct 317 ms 55084 KB Output is correct
58 Correct 1152 ms 55860 KB Output is correct
59 Correct 2499 ms 55844 KB Output is correct
60 Correct 937 ms 45600 KB Output is correct
61 Correct 1018 ms 46232 KB Output is correct
62 Correct 2221 ms 42540 KB Output is correct
63 Correct 750 ms 54592 KB Output is correct
64 Correct 58 ms 27588 KB Output is correct
65 Correct 238 ms 33096 KB Output is correct
66 Correct 464 ms 34700 KB Output is correct
67 Correct 76 ms 46408 KB Output is correct
68 Correct 338 ms 53572 KB Output is correct
69 Correct 1380 ms 56504 KB Output is correct
70 Correct 47 ms 33104 KB Output is correct
71 Correct 184 ms 33096 KB Output is correct
72 Correct 275 ms 34380 KB Output is correct
73 Correct 90 ms 54048 KB Output is correct
74 Correct 397 ms 54600 KB Output is correct
75 Correct 1104 ms 55796 KB Output is correct
76 Correct 105 ms 33408 KB Output is correct
77 Correct 232 ms 35140 KB Output is correct
78 Correct 87 ms 33664 KB Output is correct
79 Correct 217 ms 33988 KB Output is correct
80 Correct 162 ms 34452 KB Output is correct
81 Correct 56 ms 34120 KB Output is correct
82 Correct 118 ms 34436 KB Output is correct
83 Correct 46 ms 34776 KB Output is correct
84 Correct 74 ms 33476 KB Output is correct
85 Correct 49 ms 34240 KB Output is correct
86 Correct 136 ms 23772 KB Output is correct
87 Correct 48 ms 24400 KB Output is correct
88 Correct 304 ms 34844 KB Output is correct
89 Correct 260 ms 34888 KB Output is correct
90 Correct 167 ms 34332 KB Output is correct
91 Correct 152 ms 33792 KB Output is correct
92 Correct 107 ms 33352 KB Output is correct
93 Correct 258 ms 33876 KB Output is correct
94 Correct 186 ms 35616 KB Output is correct
95 Correct 158 ms 35592 KB Output is correct
96 Correct 106 ms 35944 KB Output is correct
97 Correct 82 ms 35628 KB Output is correct
98 Correct 85 ms 34060 KB Output is correct
99 Correct 83 ms 35320 KB Output is correct
100 Correct 69 ms 33864 KB Output is correct
101 Correct 66 ms 34076 KB Output is correct
102 Correct 65 ms 33864 KB Output is correct
103 Correct 52 ms 34376 KB Output is correct
104 Correct 55 ms 34172 KB Output is correct
105 Correct 49 ms 33236 KB Output is correct
106 Correct 72 ms 33692 KB Output is correct
107 Correct 426 ms 33920 KB Output is correct
108 Correct 51 ms 35140 KB Output is correct
109 Correct 222 ms 55880 KB Output is correct
110 Correct 985 ms 57016 KB Output is correct
111 Correct 2015 ms 56092 KB Output is correct
112 Correct 975 ms 55772 KB Output is correct
113 Correct 513 ms 55220 KB Output is correct
114 Correct 1275 ms 57248 KB Output is correct
115 Correct 1982 ms 56004 KB Output is correct
116 Correct 704 ms 56316 KB Output is correct
117 Correct 620 ms 49240 KB Output is correct
118 Correct 61 ms 16940 KB Output is correct
119 Correct 85 ms 17544 KB Output is correct
120 Correct 164 ms 45636 KB Output is correct
121 Correct 90 ms 57304 KB Output is correct
122 Correct 620 ms 57340 KB Output is correct
123 Correct 412 ms 55648 KB Output is correct
124 Correct 313 ms 55188 KB Output is correct
125 Correct 251 ms 54960 KB Output is correct
126 Correct 673 ms 55560 KB Output is correct
127 Correct 511 ms 55988 KB Output is correct
128 Correct 352 ms 55400 KB Output is correct
129 Correct 245 ms 55968 KB Output is correct
130 Correct 202 ms 55228 KB Output is correct
131 Correct 151 ms 55428 KB Output is correct
132 Correct 169 ms 55736 KB Output is correct
133 Correct 169 ms 56056 KB Output is correct
134 Correct 143 ms 55388 KB Output is correct
135 Correct 133 ms 55248 KB Output is correct
136 Correct 122 ms 55436 KB Output is correct
137 Correct 99 ms 55292 KB Output is correct
138 Correct 91 ms 55208 KB Output is correct
139 Correct 102 ms 56236 KB Output is correct
140 Correct 92 ms 54596 KB Output is correct
141 Correct 115 ms 54192 KB Output is correct
142 Correct 156 ms 55224 KB Output is correct
143 Correct 90 ms 58252 KB Output is correct