oj.uz

답안 #239742

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
239742 2020-06-17T08:34:45 Z Vimmer Clickbait (COCI18_clickbait) C++14
120 / 120
 15 ms 5376 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[10000];

int a[1005][1005];

a4 pos[10000];

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] == '+')) {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 != 0)
            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
120.0 / 120.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 896 KB Output is correct
2 Correct 5 ms 768 KB Output is correct
3 Correct 5 ms 896 KB Output is correct
4 Correct 5 ms 768 KB Output is correct
5 Correct 5 ms 768 KB Output is correct
6 Correct 5 ms 768 KB Output is correct
7 Correct 5 ms 768 KB Output is correct
8 Correct 5 ms 1152 KB Output is correct
9 Correct 6 ms 2560 KB Output is correct
10 Correct 15 ms 5376 KB Output is correct