Submission #47167

#	Time	Username	Problem	Language	Result	Execution time	Memory
47167		Bruteforceman	Clickbait (COCI18_clickbait)	C++11	120 / 120	97 ms	39124 KiB

clickbait

#include "bits/stdc++.h"
using namespace std;
int n, m;
char s[1111][1111];
bool vis[1111][1111];
const int dx[] = {-1, 1, 0, 0};
const int dy[] = {0, 0, 1, -1};
int a[1111][1111];
int id[1111][1111];

bool inside(int x, int y) {
	if(0 <= x && x < n) {
		if(0 <= y && y < m) {
			return true;
		}
	}
	return false;
}
bool outline(int i, int j) {
	return (s[i][j] == '-' || s[i][j] == '|' || s[i][j] == '+');
}

int val;

int get(int x, int y) {
	while(y > 0 && isdigit(s[x][y-1])) {
		--y;
	}
	int ans = 0;
	while(y < m && isdigit(s[x][y])) {
		ans = 10 * ans + (s[x][y] - '0');
		++y;
	}
	return ans;
}

void fill(int x, int y) {
	vis[x][y] = true;
	if(isdigit(s[x][y])) {
		val = get(x, y);
	}
 	for(int i = 0; i < 4; i++) {
		int p = x + dx[i];
		int q = y + dy[i];
		if(inside(p, q) && vis[p][q] == false && (s[p][q] == '.' || isdigit(s[p][q]))) {
			fill(p, q);
		}
	}
}

void mark(int x, int y) {
	a[x][y] = val; 
 	for(int i = 0; i < 4; i++) {
		int p = x + dx[i];
		int q = y + dy[i];
		if(inside(p, q) && a[p][q] == 0 && (s[p][q] == '.' || isdigit(s[p][q]))) {
			mark(p, q);
		}
	}
} 

int container(int x, int y) {
	for(int i = 0; i < 4; i++) {
		int p = x + dx[i];
		int q = y + dy[i];
		if(inside(p, q) && id[p][q] > 0) return id[p][q];
	}
	return 0;
}

int root;
int child;

void finder(int x, int y) {
	// cout << x << "--" << y << endl;
	vis[x][y] = true;
	int ad = container(x, y);
	if(ad > 0 && ad != root) {
		child = ad;
		return ;
	}
	for(int i = 0; i < 4; i++) {
		int p = x + dx[i];
		int q = y + dy[i];
		if(inside(p, q) && vis[p][q] == false && outline(p, q) && id[p][q] == 0) {
			finder(p, q);
		}
	}
}


typedef pair <int, int> pii;
vector <pii> g[1000010];

void trav(int x) {
	sort(g[x].begin(), g[x].end());
	reverse(g[x].begin(), g[x].end());
	for(auto i : g[x]) {
		trav(i.second);
	}
	printf("%d\n", x);
}

int main(int argc, char const *argv[])
{
	scanf("%d %d", &n, &m);
	for(int i = 0; i < n; i++) {
		scanf("%s", s[i]);
	}	
	for(int i = 0; i < n; i++) {
		for(int j = 0; j < m; j++) {
			if(vis[i][j] == false) {
				if(isdigit(s[i][j]) || s[i][j] == '.') {
					val = -1;
					fill(i, j);
					if(val != -1) {
						mark(i, j);
					}
				}
			} 
		}
	}
	for(int i = 0; i < n; i++) {
		for(int j = 0; j < m; j++) {
			id[i][j] = a[i][j];
			if(outline(i, j)) {
				for(int x = -1; x <= 1; x++) {
					for(int y = -1; y <= 1; y++) {
						int p = i + x;
						int q = j + y;
						if(inside(p, q) && a[p][q] > 0) {
							id[i][j] = a[p][q];
						}
					}
				} 
			}
		}
	}
/*
	for(int i = 0; i < n; i++) {
		for(int j = 0; j < m; j++) {
			cout << id[i][j] << " ";
		}
		cout << endl;
	}
*/
	memset(vis, false, sizeof vis);
	for(int i = 0; i < n; i++) {
		for(int j = 0; j < m; j++) {
			if(id[i][j] == 0 && vis[i][j] == false && s[i][j] == '-' && container(i, j)) {
				root = container(i, j);
				finder(i, j);
				g[root].push_back(pii(i, child));
				// cout << root << " " << child << endl;
			}
		}
	}
	trav(1);
	return 0;
}

Compilation message (stderr)

clickbait.cpp: In function 'int main(int, const char**)':
clickbait.cpp:106:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d", &n, &m);
  ~~~~~^~~~~~~~~~~~~~~~~
clickbait.cpp:108:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%s", s[i]);
   ~~~~~^~~~~~~~~~~~

• Subtask 1: 120 / 120