Submission #650207

#	Time	Username	Problem	Language	Result	Execution time	Memory
650207		inksamurai	Clickbait (COCI18_clickbait)	C++17	120 / 120	26 ms	10316 KiB

clickbait

#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
#define rng(i,c,n) for(int i=c;i<n;i++)
#define per(i,n) for(int i=n-1;i>=0;i--)
#define fi first
#define se second
#define pb push_back
#define sz(a) (int)a.size()
#define vec(...) vector<__VA_ARGS__>
#define _3yqVz8E ios::sync_with_stdio(0),cin.tie(0)
typedef long long ll;
using pii=pair<int,int>;
using vi=vector<int>;
void print(){cout<<'\n';}
template<class h,class...t>
void print(const h&v,const t&...u){cout<<v<<' ',print(u...);}
// e

signed main(){
_3yqVz8E;
	int h,w;
	cin>>h>>w;
	vec(vec(char)) a(h,vec(char)(w));
	rep(i,h){
		rep(j,w){
			cin>>a[i][j];
		}
	}
	const int di[]={1,-1,0,0};
	const int dj[]={0,0,1,-1};
	auto ok=[&](int i,int j)->bool{
		return i>=0 and j>=0 and i<h and j<w;
	};
	vec(vi) usd(h,vi(w));
	vi lebs;
	using Fp=pair<pii,pii>;
	map<int,Fp> loc;
	rep(i,h){
		rep(j,w){
			if(usd[i][j]) continue;
			if(a[i][j]!='.' and a[i][j]!='+' and a[i][j]!='-' and a[i][j]!='|'){
				assert(a[i][j]>='0' and a[i][j]<='9');
				int nj=j;
				int v=0;
				while(a[i][nj]>='0' and a[i][nj]<='9'){
					v=v*10+(a[i][nj]-'0');
					nj+=1;
				}
				lebs.pb(v);
				queue<pii> que;				
				que.push({i,j});
				usd[i][j]=v;
				int sx=i,sy=j,tx=i,ty=j;
				while(sz(que)){
					auto top=que.front();
					que.pop();
					pii p=top;
					rep(dir,4){
						int ni=p.fi+di[dir];
						int nj=p.se+dj[dir];
						if(ok(ni,nj) and !usd[ni][nj]){
							usd[ni][nj]=v;
							sx=min(sx,ni);
							sy=min(sy,nj);
							tx=max(tx,ni);
							ty=max(ty,nj);
							if(a[ni][nj]=='+' or a[ni][nj]=='-' or a[ni][nj]=='|'){
							}else{
								que.push({ni,nj});
							}
						}
					}
				}
				loc[v]={{sx,sy},{tx,ty}};
			}
		}
	}
	vec(vi) visited(h,vi(w));
	auto find_path_=[&](auto self,int sx,int sy,int dir)->int{
		assert(ok(sx,sy) and !visited[sx][sy]);
		visited[sx][sy]=1;
		if(a[sx][sy]=='-' or a[sx][sy]=='|'){
			sx+=di[dir];
			sy+=dj[dir];
			return self(self,sx,sy,dir);
		}else{
			if(usd[sx][sy]!=0){
				return usd[sx][sy];
			}else{
				assert(a[sx][sy]=='+');
				// print(sx,sy,a[sx][sy],dir);
				if(dir==0){
					if(ok(sx,sy-1) and a[sx][sy-1]=='-'){
						dir=3;
					}else{
						dir=2;
					}
				}else{
					dir=0;
				}
				sx+=di[dir];
				sy+=dj[dir];
				return self(self,sx,sy,dir);
			}
		}
	};
	vi pns;
	auto dfs=[&](auto self,int v)->void{
		// pns.pb(v);
		pii s=loc[v].fi;
		pii t=loc[v].se;
		for(int i=t.fi;i>=s.fi;i--){
			int l=s.se-1;
			int r=t.se+1;
			if(ok(i,r) and a[i][r]=='-'){
				// print(i,r);
				int u=find_path_(find_path_,i,r,2);
				self(self,u);
			}
			if(ok(i,l) and a[i][l]=='-'){
				int u=find_path_(find_path_,i,l,3);
				self(self,u);
			}
		}
		pns.pb(v);
	};
	dfs(dfs,1);
	// reverse(pns.begin(), pns.end());
	for(auto v:pns){
		cout<<v<<" ";
	}
}

• Subtask 1: 120 / 120