oj.uz

Submission #239733

# Submission time Handle Problem Language Result Execution time Memory
239733 2020-06-17T08:23:54 Z Vimmer Clickbait (COCI18_clickbait) C++14
60 / 120
 17 ms 10496 KB 
#include <bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>

//#pragma GCC optimize("unroll-loops")
//#pragma GCC optimize("-O3")
//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("fast-math")
//#pragma GCC optimize("no-stack-protector")

#define F first
#define S second
#define sz(x) int(x.size())
#define pb push_back
#define N 101001
#define M ll(1e9 + 7)
#define inf 1e9 + 1e9


using namespace std;
//using namespace __gnu_pbds;

typedef long double ld;
typedef long long ll;
typedef short int si;
typedef array <int, 4> a4;

//typedef tree <int, null_type, less_equal<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;



vector <pair <int, int> > g[40];

int a[1005][1005];

a4 pos[40];

string s[1005];

int b[4][2] = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}}, n, m;

vector <int> ans;

void dfs(int v)
{
    for (auto it : g[v]) dfs(it.S);

    ans.pb(v);
}
void rec(int x, int y, int nm, int px, int py, int h)
{
    for (int i = 0; i < 4; i++)
    {
        int cx = x + b[i][0];

        int cy = y + b[i][1];

        if (cx == px && cy == py) continue;

        if (cx < 0 || cx >= n || cy < 0 || cy >= m || s[cx][cy] == '.') continue;

        if (s[cx][cy] != s[x][y] && s[x][y] != '+' && s[cx][cy] != '+') g[nm].pb({h, a[cx][cy]});
            else
            {
                px = x; py = y;

                x = cx; y = cy;

                i = -1;

                continue;
            }

        return;
    }
}

int main()
{
    //freopen("input.txt", "r", stdin); //freopen("output4.txt", "w", stdout);

    ios_base::sync_with_stdio(0); istream::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    cin >> n >> m;

    for (int i = 0; i < n; i++) cin >> s[i];

    int mx = 0;

    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
        {
            if (s[i][j] == '.' || s[i][j] == '-' || s[i][j] == '|' || s[i][j] == '+' || a[i][j] != 0) continue;

            int nm = 0; mx = max(mx, nm);

            int pj = j;

            while (!(s[i][pj] == '.' || s[i][pj] == '-' || s[i][pj] == '|' || s[i][pj] == '+')) pj++;

            pj--;

            while (pj >= j) {nm *= 10; nm += s[i][pj] - '0'; pj--;}

            mx = max(mx, nm);

            int xl = i, xr = i, yl = j, yr = j;

            while (s[xr][j] != '-') xr++;

            while (s[xl][j] != '-') xl--;

            while (s[i][yr] != '|') yr++;

            while (s[i][yl] != '|') yl--;

            for (int x = xl; x <= xr; x++)
                for (int y = yl; y <= yr; y++) a[x][y] = nm;

            pos[nm] = {xl, yl, xr, yr};
        }

    for (int nm = 1; nm <= mx; nm++)
    {
        int xl = pos[nm][0], yl = pos[nm][1], xr = pos[nm][2], yr = pos[nm][3];

        if (yl - 1 != -1)
            for (int x = xl; x <= xr; x++)
              if (s[x][yl - 1] == '-')
                rec(x, yl - 1, nm, x, yl, x);

        if (yr + 1 != m)
            for (int x = xl; x <= xr; x++)
              if (s[x][yr + 1] == '-')
                rec(x, yr + 1, nm, x, yr, x);
    }

    for (int i = 1; i <= mx; i++) {sort(g[i].begin(), g[i].end()); reverse(g[i].begin(), g[i].end());}

    dfs(1);

    for (auto it : ans) cout << it << endl;
}

Subtask #1
60.0 / 120.0

# Verdict Execution time Memory Grader output
1 Runtime error 8 ms 1280 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Runtime error 6 ms 896 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Runtime error 5 ms 1024 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Correct 5 ms 384 KB Output is correct
5 Correct 5 ms 512 KB Output is correct
6 Correct 5 ms 512 KB Output is correct
7 Correct 5 ms 512 KB Output is correct
8 Correct 5 ms 896 KB Output is correct
9 Runtime error 12 ms 4736 KB Execution killed with signal 11 (could be triggered by violating memory limits)
10 Runtime error 17 ms 10496 KB Execution killed with signal 11 (could be triggered by violating memory limits)