Submission #312065

#	Time	Username	Problem	Language	Result	Execution time	Memory
312065		colazcy	Clickbait (COCI18_clickbait)	C++17	120 / 120	35 ms	33656 KiB

clickbait

#include <cstdio>
#include <cctype>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;
const int maxn = 1024;
char mp[maxn][maxn];
int n,m,tot,ans[maxn * maxn],id[maxn][maxn],vis[maxn][maxn],deltax[] = {-1,1,0,0},deltay[] = {0,0,-1,1};
inline bool chk(int x,int y){
	return x >= 1 && x <= n && y >= 1 && y <= m;
}
struct point{int x,y;};
inline void bfs(point s,int col){
	queue<point> q;
	q.push(s);vis[s.x][s.y] = 1;
	while(!q.empty()){
		point now = q.front();q.pop();
		id[now.x][now.y] = col;
		for(int i = 0;i < 4;i++){
			int nx = now.x + deltax[i],ny = now.y + deltay[i];
			if(!chk(nx,ny) || vis[nx][ny])continue;
			if(mp[nx][ny] == '.' || isdigit(mp[nx][ny]))q.push(point{nx,ny}),vis[nx][ny] = 1;
			else id[nx][ny] = col,vis[nx][ny] = 1;
		}
	}
}
inline int find(point now){
	while(!id[now.x][now.y]){
		vis[now.x][now.y] = 1;
		if(mp[now.x][now.y] == '-'){
			if(!vis[now.x][now.y - 1])now.y--;
			else if(!vis[now.x][now.y + 1])now.y++;
		}else if(mp[now.x][now.y] == '|')now.x++;
		else if(mp[now.x][now.y] == '+'){
			for(int i = 0;i < 4;i++){
				int nx = now.x + deltax[i],ny = now.y + deltay[i];
				if(chk(nx,ny) && !vis[nx][ny] && mp[nx][ny] != '.'){
					now.x = nx,now.y = ny;
					break;
				}
			}
		}
	}
	return id[now.x][now.y];
}
struct edge{
	int v,d;
	bool operator < (const edge &rhs)const{
		return d > rhs.d;
	}
};
vector<edge> G[maxn * maxn];
inline void addedge(int u,int v,int d){
	G[u].push_back(edge{v,d});
}
inline void dfs(int u){
	for(int i = 0;i < G[u].size();i++){
		int v = G[u][i].v;
		dfs(v);
	}
	ans[++tot] = u;
}
int main(){
//	freopen("clickbait.in","r",stdin);
//	freopen("clickbait.out","w",stdout);
	scanf("%d %d",&n,&m);
	for(int i = 1;i <= n;i++)scanf("%s",mp[i] + 1);
	for(int i = 1;i <= n;i++)
		for(int j = 1;j <= m;j++)
			if(isdigit(mp[i][j])){
				int now = 0;
				for(int k = j;isdigit(mp[i][k]);j = k,k++)now = now * 10 + mp[i][k] - '0';
				bfs(point{i,j},now);
			}
	for(int i = 1;i <= n;i++)
		for(int j = 1;j <= m;j++)
			if(mp[i][j] == '|')
				if(mp[i][j - 1] == '-')addedge(id[i][j],find(point{i,j - 1}),i);
				else if(mp[i][j + 1] == '-')addedge(id[i][j],find(point{i,j + 1}),i);
	for(int i = 1;i < maxn * maxn;i++)
		if(G[i].size() > 1)sort(G[i].begin(),G[i].end());
	dfs(1);
	for(int i = 1;i <= tot;i++)printf("%d\n",ans[i]);
	return 0;
}

Compilation message (stderr)

clickbait.cpp: In function 'void dfs(int)':
clickbait.cpp:58:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<edge>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   58 |  for(int i = 0;i < G[u].size();i++){
      |                ~~^~~~~~~~~~~~~
clickbait.cpp: In function 'int main()':
clickbait.cpp:78:6: warning: suggest explicit braces to avoid ambiguous 'else' [-Wdangling-else]
   78 |    if(mp[i][j] == '|')
      |      ^
clickbait.cpp:67:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   67 |  scanf("%d %d",&n,&m);
      |  ~~~~~^~~~~~~~~~~~~~~
clickbait.cpp:68:32: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   68 |  for(int i = 1;i <= n;i++)scanf("%s",mp[i] + 1);
      |                           ~~~~~^~~~~~~~~~~~~~~~

• Subtask 1: 120 / 120