oj.uz

Submission #197001

# Submission time Handle Problem Language Result Execution time Memory
197001 2020-01-18T03:25:32 Z combi1k1 Dango Maker (JOI18_dango_maker) C++14
13 / 100
 247 ms 212600 KB 
#include<bits/stdc++.h>

using namespace std;

#define ll  long long
#define ld  double

#define sz(x)   (int)x.size()
#define all(x)  x.begin(),x.end()

#define pb  emplace_back
#define X   first
#define Y   second

const int   N   = 3005;

typedef pair<int,int>   ii;

char a[N][N];
int  t[N][N];

struct Edge {
    int v, c;
    Edge(int _v,int _c) : v(_v), c(_c)  {}
};

vector<Edge> E;
vector<int>  g[N * N];

void addEdge(int u,int v,int c) {
    g[u].pb(sz(E)); E.pb(v,c);
    g[v].pb(sz(E)); E.pb(u,0);
}

int S, T;
int d[N * N];
int p[N * N];

bool bfs()  {
    for(int i = 0 ; i <= T ; ++i)
        d[i] = -1,
        p[i] = 0;

    queue<int>  q;
    q.push(S);  d[S] = 0;

    while (q.size())    {
        int u = q.front();  q.pop();
        for(int i : g[u])   {
            int v = E[i].v;
            if (E[i].c == 0)    continue;
            if (d[v] < 0)   {
                d[v] = d[u] + 1;
                q.push(v);
            }
        }
    }

    return  d[T] >= 0;
}

int dfs(int u,int F)    {
    if (u == T || F == 0)   return  F;
    for(int &i = p[u] ; i < sz(g[u]) ; ++i)  {
        int j = g[u][i];
        int v = E[j].v;
        if (E[j].c == 0 || d[v] != d[u] + 1)
            continue;
        int res = dfs(v,min(E[j].c,F));
        if (res)    {
            E[j].c -= res;  j ^= 1;
            E[j].c += res;  return  res;
        }
    }
    return  0;
}

int MaxFlow()   {
    while (bfs())
    while (dfs(S,1));

    int ans = 0;

    for(int i : g[T])
        ans += E[i].c;

    return  ans;
}

int main()  {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    int n;  cin >> n;
    int m;  cin >> m;

    int cnt = 0;

    for(int i = 0 ; i < n ; ++i)
    for(int j = 0 ; j < m ; ++j)    {
        cin >> a[i][j];

        if (a[i][j] != 'G')
            t[i][j] = cnt++;

        if (a[i][j] == 'W') {
            if (i > 1 && a[i - 1][j] == 'G' && a[i - 2][j] == 'R')
                addEdge(t[i][j],t[i - 2][j],1);
            if (j > 1 && a[i][j - 1] == 'G' && a[i][j - 2] == 'R')
                addEdge(t[i][j],t[i][j - 2],1);
        }
    }
    S = cnt;
    T = cnt + 1;

    for(int i = 0 ; i < n ; ++i)
    for(int j = 0 ; j < m ; ++j)    {
        if (a[i][j] == 'W') addEdge(S,t[i][j],1);
        if (a[i][j] == 'R') addEdge(t[i][j],T,1);
    }

    cout << MaxFlow() << endl;
}

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 206 ms 212472 KB Output is correct
2 Correct 208 ms 212472 KB Output is correct
3 Correct 208 ms 212444 KB Output is correct
4 Correct 229 ms 212464 KB Output is correct
5 Correct 238 ms 212472 KB Output is correct
6 Correct 247 ms 212452 KB Output is correct
7 Correct 244 ms 212600 KB Output is correct
8 Correct 241 ms 212472 KB Output is correct
9 Correct 238 ms 212348 KB Output is correct
10 Correct 237 ms 212392 KB Output is correct
11 Correct 209 ms 212476 KB Output is correct
12 Correct 214 ms 212468 KB Output is correct
13 Correct 207 ms 212460 KB Output is correct
14 Correct 228 ms 212472 KB Output is correct
15 Correct 207 ms 212368 KB Output is correct
16 Correct 242 ms 212344 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 206 ms 212472 KB Output is correct
2 Correct 208 ms 212472 KB Output is correct
3 Correct 208 ms 212444 KB Output is correct
4 Correct 229 ms 212464 KB Output is correct
5 Correct 238 ms 212472 KB Output is correct
6 Correct 247 ms 212452 KB Output is correct
7 Correct 244 ms 212600 KB Output is correct
8 Correct 241 ms 212472 KB Output is correct
9 Correct 238 ms 212348 KB Output is correct
10 Correct 237 ms 212392 KB Output is correct
11 Correct 209 ms 212476 KB Output is correct
12 Correct 214 ms 212468 KB Output is correct
13 Correct 207 ms 212460 KB Output is correct
14 Correct 228 ms 212472 KB Output is correct
15 Correct 207 ms 212368 KB Output is correct
16 Correct 242 ms 212344 KB Output is correct
17 Incorrect 235 ms 212472 KB Output isn't correct
18 Halted 0 ms 0 KB -

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 206 ms 212472 KB Output is correct
2 Correct 208 ms 212472 KB Output is correct
3 Correct 208 ms 212444 KB Output is correct
4 Correct 229 ms 212464 KB Output is correct
5 Correct 238 ms 212472 KB Output is correct
6 Correct 247 ms 212452 KB Output is correct
7 Correct 244 ms 212600 KB Output is correct
8 Correct 241 ms 212472 KB Output is correct
9 Correct 238 ms 212348 KB Output is correct
10 Correct 237 ms 212392 KB Output is correct
11 Correct 209 ms 212476 KB Output is correct
12 Correct 214 ms 212468 KB Output is correct
13 Correct 207 ms 212460 KB Output is correct
14 Correct 228 ms 212472 KB Output is correct
15 Correct 207 ms 212368 KB Output is correct
16 Correct 242 ms 212344 KB Output is correct
17 Incorrect 235 ms 212472 KB Output isn't correct
18 Halted 0 ms 0 KB -