Submission #126153

#	Time	Username	Problem	Language	Result	Execution time	Memory
126153		choikiwon	Sandwich (JOI16_sandwich)	C++17	0 / 100	497 ms	20856 KiB

sandwich

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

const int MN = 444;

ll cross(pii a, pii b) {
    return 1LL * a.first * b.second - 1LL * a.second * b.first;
}
ll ccw(pii a, pii b, pii c) {
    pii p = pii(b.first - a.first, b.second - a.second);
    pii q = pii(c.first - a.first, c.second - a.second);
    return cross(p, q);
}

int N, M;
char G[MN][MN];
vector<int> adj[MN * MN * 2], radj[MN * MN * 2];
int deg[MN * MN * 2], sz[MN * MN * 2];

int f(int r, int c, int up) {
    return 2 * (r * M + c) + up;
}
pii g(int x) {
    return pii((x / 2) / M, (x / 2) % M);
}

int vis[MN * MN * 2];
int X;

void go(int u, int dir) {
    if(vis[u] == 1) {
        X = u;
        return;
    }
    vis[u] = 1;
    if(radj[u].size() == 0) return;
    if(radj[u].size() == 1) {
        go(radj[u][0], dir);
        return;
    }
    int x = radj[u][0];
    int y = radj[u][1];

    if((ccw(g(u), g(x), g(y)) > 0) == dir) go(y, dir);
    else go(x, dir);
}

int find(int u) {
    if(radj[u].size() < 2) return -1;

    int x = radj[u][0];
    int y = radj[u][1];
    if(deg[x] || deg[y]) return -1;

    memset(vis, 0, sizeof(vis));
    X = -1;

    go(x, ccw(g(u), g(x), g(y)) > 0);
    go(y, ccw(g(u), g(y), g(x)) > 0);

    return X;
}

int main() {
    scanf("%d %d", &N, &M);

    for(int i = 0; i < N; i++) {
        scanf("\n");
        for(int j = 0; j < M; j++) {
            scanf("%c", &G[i][j]);
        }
    }

    for(int i = 0; i < N; i++) {
        for(int j = 0; j < M; j++) {
            if(G[i][j] == 'N') {
                if(i) adj[ f(i - 1, j, 1) ].push_back(f(i, j, 1)), deg[ f(i, j, 1) ]++;
                if(j < M - 1) adj[ f(i, j + 1, G[i][j + 1] == 'N') ].push_back(f(i, j, 1)), deg[ f(i, j, 1) ]++;
                if(i < N - 1) adj[ f(i + 1, j, 0) ].push_back(f(i, j, 0)), deg[ f(i, j, 0) ]++;
                if(j) adj[ f(i, j - 1, G[i][j - 1] == 'Z') ].push_back(f(i, j, 0)), deg[ f(i, j, 0) ]++;
            }
            if(G[i][j] == 'Z') {
                if(i) adj[ f(i - 1, j, 1) ].push_back(f(i, j, 1)), deg[ f(i, j, 1) ]++;
                if(j) adj[ f(i, j - 1, G[i][j - 1] == 'Z') ].push_back(f(i, j, 1)), deg[ f(i, j, 1) ]++;
                if(i < N - 1) adj[ f(i + 1, j, 0) ].push_back(f(i, j, 0)), deg[ f(i, j, 0) ]++;
                if(j < M - 1) adj[ f(i, j + 1, G[i][j + 1] == 'N') ].push_back(f(i, j, 0)), deg[ f(i, j, 0) ]++;
            }
        }
    }
    for(int u = 0; u < N * M * 2; u++) {
        for(int i = 0; i < adj[u].size(); i++) {
            int v = adj[u][i];
            radj[v].push_back(u);
        }
    }

    queue<int> q;
    for(int i = 0; i < N * M * 2; i++) if(!deg[i]) {
        q.push(i);
    }
    while(!q.empty()) {
        int u = q.front(); q.pop();
        sz[u]++;

        int x = find(u);
        if(x != -1) sz[u] -= sz[x];

        for(int i = 0; i < adj[u].size(); i++) {
            int v = adj[u][i];

            sz[v] += sz[u];
            deg[v]--;
            if(!deg[v]) {
                q.push(v);
            }
        }
    }

    for(int i = 0; i < N; i++) {
        for(int j = 0; j < M; j++) {
            int t1 = deg[ f(i, j, 1) ] == 0? sz[ f(i, j, 1) ] : 1e9;
            int t2 = deg[ f(i, j, 0) ] == 0? sz[ f(i, j, 0) ] : 1e9;
            if(min(t1, t2) == 1e9) printf("-1 ");
            else printf("%d ", 2 * min(t1, t2));
        }
        printf("\n");
    }
}

Compilation message (stderr)

sandwich.cpp: In function 'int main()':
sandwich.cpp:94:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int i = 0; i < adj[u].size(); i++) {
                        ~~^~~~~~~~~~~~~~~
sandwich.cpp:111:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int i = 0; i < adj[u].size(); i++) {
                        ~~^~~~~~~~~~~~~~~
sandwich.cpp:68:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d", &N, &M);
     ~~~~~^~~~~~~~~~~~~~~~~
sandwich.cpp:71:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("\n");
         ~~~~~^~~~~~
sandwich.cpp:73:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%c", &G[i][j]);
             ~~~~~^~~~~~~~~~~~~~~~

• Subtask 1: 0 / 35
• Subtask 2: 0 / 65