oj.uz

Submission #680351

# Submission time Handle Problem Language Result Execution time Memory
680351 2023-01-10T16:10:36 Z kakayoshi Dango Maker (JOI18_dango_maker) C++14
33 / 100
 35 ms 28788 KB 
#include <bits/stdc++.h>
using namespace std;

#define forw(i,a,b) for(ll i=a;i<=b;i++)
#define forb(i,a,b) for(ll i=a;i>=b;i--)
#define pu push
#define pb push_back
#define fi first
#define se second
#define all(a) a.begin(),a.end()
#define minimize(a,b) a=min(a,b)
#define maximize(a,b) a=max(a,b)
typedef long long int ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef pair<ll,pair<ll,ll> > plll;
const int maxN=3000+5;
const ll oo=1e18;
const char base[3]={'R','G','W'};
const int tx[2]={1,0};
const int ty[2]={0,1};
bool vis1[maxN];
int n,m,match[maxN],cnt,vis[maxN][maxN];
char a[maxN][maxN];
vector <int> edge[maxN];
bool outmap(int x, int y)
{
    if (1<=x && x<=n)
    if (1<=y && y<=m) return 0;
    return 1;
}
bool matching(int u)
{
    for(int v:edge[u])
    if (!vis1[v])
    {
        vis1[v]=1;
        if (!match[v] || matching(match[v]))
        {
            match[v]=u;
            return 1;
        }
    }
    return 0;
}
void solve()
{
    cin>>n>>m;
    forw(i,1,n)
    forw(j,1,m)
        cin>>a[i][j];
    forw(i,1,n)
    forw(j,1,m)
    if (a[i][j]==base[0])
    forw(p,0,1)
    {
        int x=i; int y=j;
        bool flag=1;
        forw(k,1,2)
        {
            x+=tx[p]; y+=ty[p];
            if (outmap(x,y) || a[x][y]!=base[k]) flag=0;
        }
        if (!flag) continue;
        x=i; y=j;
        //cout<<x<<" "<<y<<endl;
        cnt++;
        if (vis[x][y])
        {
            edge[cnt].pb(vis[x][y]);
            edge[vis[x][y]].pb(cnt);
            //cout<<"meet: "<<cnt<<" "<<vis[x][y]<<" "<<x<<" "<<y<<" "<<0<<endl;
        }
        vis[x][y]=cnt;
        forw(k,1,2)
        {
            x+=tx[p]; y+=ty[p];
            if (vis[x][y])
            {
                edge[cnt].pb(vis[x][y]);
                edge[vis[x][y]].pb(cnt);
                //cout<<"meet: "<<cnt<<" "<<vis[x][y]<<" "<<x<<" "<<y<<" "<<k<<endl;
            }
            vis[x][y]=cnt;
        }
    }
    int ans=0;
    forw(i,1,cnt)
    {
        memset(vis1,0,sizeof vis1);
        ans+=matching(i);
    }
    cout<<cnt-ans/2;
    return;
}
int main()
{
    ios::sync_with_stdio();
    cin.tie(0);
    //freopen("bruh.inp","r",stdin);
    //freopen("bruh.out","w",stdout);
    solve();
    return 0;
}

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 0 ms 340 KB Output is correct
10 Correct 0 ms 340 KB Output is correct
11 Correct 0 ms 340 KB Output is correct
12 Correct 0 ms 340 KB Output is correct
13 Correct 0 ms 340 KB Output is correct
14 Correct 0 ms 340 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 0 ms 340 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 0 ms 340 KB Output is correct
10 Correct 0 ms 340 KB Output is correct
11 Correct 0 ms 340 KB Output is correct
12 Correct 0 ms 340 KB Output is correct
13 Correct 0 ms 340 KB Output is correct
14 Correct 0 ms 340 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 0 ms 340 KB Output is correct
17 Correct 0 ms 340 KB Output is correct
18 Correct 0 ms 340 KB Output is correct
19 Correct 1 ms 340 KB Output is correct
20 Correct 0 ms 340 KB Output is correct
21 Correct 1 ms 340 KB Output is correct
22 Correct 1 ms 340 KB Output is correct
23 Correct 1 ms 340 KB Output is correct
24 Correct 0 ms 340 KB Output is correct
25 Correct 0 ms 340 KB Output is correct
26 Correct 0 ms 340 KB Output is correct
27 Correct 0 ms 340 KB Output is correct
28 Correct 1 ms 468 KB Output is correct
29 Correct 1 ms 340 KB Output is correct
30 Correct 1 ms 340 KB Output is correct
31 Correct 1 ms 340 KB Output is correct
32 Correct 1 ms 376 KB Output is correct
33 Correct 1 ms 468 KB Output is correct
34 Correct 1 ms 376 KB Output is correct
35 Correct 1 ms 376 KB Output is correct
36 Correct 1 ms 340 KB Output is correct
37 Correct 1 ms 468 KB Output is correct
38 Correct 1 ms 376 KB Output is correct
39 Correct 1 ms 468 KB Output is correct
40 Correct 1 ms 468 KB Output is correct
41 Correct 1 ms 468 KB Output is correct
42 Correct 1 ms 468 KB Output is correct
43 Correct 1 ms 380 KB Output is correct
44 Correct 0 ms 468 KB Output is correct
45 Correct 1 ms 372 KB Output is correct
46 Correct 1 ms 340 KB Output is correct
47 Correct 1 ms 340 KB Output is correct
48 Correct 1 ms 340 KB Output is correct
49 Correct 1 ms 468 KB Output is correct
50 Correct 1 ms 468 KB Output is correct
51 Correct 1 ms 340 KB Output is correct
52 Correct 1 ms 376 KB Output is correct
53 Correct 1 ms 356 KB Output is correct

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 0 ms 340 KB Output is correct
10 Correct 0 ms 340 KB Output is correct
11 Correct 0 ms 340 KB Output is correct
12 Correct 0 ms 340 KB Output is correct
13 Correct 0 ms 340 KB Output is correct
14 Correct 0 ms 340 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 0 ms 340 KB Output is correct
17 Correct 0 ms 340 KB Output is correct
18 Correct 0 ms 340 KB Output is correct
19 Correct 1 ms 340 KB Output is correct
20 Correct 0 ms 340 KB Output is correct
21 Correct 1 ms 340 KB Output is correct
22 Correct 1 ms 340 KB Output is correct
23 Correct 1 ms 340 KB Output is correct
24 Correct 0 ms 340 KB Output is correct
25 Correct 0 ms 340 KB Output is correct
26 Correct 0 ms 340 KB Output is correct
27 Correct 0 ms 340 KB Output is correct
28 Correct 1 ms 468 KB Output is correct
29 Correct 1 ms 340 KB Output is correct
30 Correct 1 ms 340 KB Output is correct
31 Correct 1 ms 340 KB Output is correct
32 Correct 1 ms 376 KB Output is correct
33 Correct 1 ms 468 KB Output is correct
34 Correct 1 ms 376 KB Output is correct
35 Correct 1 ms 376 KB Output is correct
36 Correct 1 ms 340 KB Output is correct
37 Correct 1 ms 468 KB Output is correct
38 Correct 1 ms 376 KB Output is correct
39 Correct 1 ms 468 KB Output is correct
40 Correct 1 ms 468 KB Output is correct
41 Correct 1 ms 468 KB Output is correct
42 Correct 1 ms 468 KB Output is correct
43 Correct 1 ms 380 KB Output is correct
44 Correct 0 ms 468 KB Output is correct
45 Correct 1 ms 372 KB Output is correct
46 Correct 1 ms 340 KB Output is correct
47 Correct 1 ms 340 KB Output is correct
48 Correct 1 ms 340 KB Output is correct
49 Correct 1 ms 468 KB Output is correct
50 Correct 1 ms 468 KB Output is correct
51 Correct 1 ms 340 KB Output is correct
52 Correct 1 ms 376 KB Output is correct
53 Correct 1 ms 356 KB Output is correct
54 Correct 1 ms 372 KB Output is correct
55 Correct 5 ms 10488 KB Output is correct
56 Correct 2 ms 468 KB Output is correct
57 Runtime error 35 ms 28788 KB Execution killed with signal 11
58 Halted 0 ms 0 KB -