Submission #824048

#	Time	Username	Problem	Language	Result	Execution time	Memory
824048		MohamedAliSaidane	Dango Maker (JOI18_dango_maker)	C++14	33 / 100	2068 ms	201920 KiB

dango_maker

    #include<bits/stdc++.h>
    #pragma GCC optimize("O3,unroll-loops")
	#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
    using namespace std;
     
    typedef long long ll;
     
    #define ff first
    #define ss second
    #define pb push_back
    #define all(x) (x).begin(),(x).end()
     
    const int nax = 3005;
    const int MOD = 1e9 + 7;
    int n, m;
    char grid[nax][nax];
    int uses[nax][nax];
    vector<int> p, setsz, seen;
    vector<int> R, T;
    int dp[2][2][2][2];
    unordered_map<int,vector<int>> comp;
    int findset(int x){return p[x] = p[x] == x? x: findset(p[x]);}
    void unite(int i, int j)
    {
    	int x = findset(i);
    	int y = findset(j);
    	if(x == y)
    		return ;
    	if(setsz[x] > setsz[y])
    		swap(x, y);
    	p[x] = y;
    	setsz[y] += setsz[x];
    	return ; 
    }
    bool cmp(int i, int j)
    {
    	if(R[i] == R[j])
    		return T[i] < T[j];
    	else
    		return R[i] < R[j];
    }
    bool collision(int i, int j)
    {
    	if(T[i] == T[j])
    		return false;
    	if(R[i] > R[j])
    		swap(i, j);
    	if(R[i] == R[j])
    		return true;
    	if(R[j] <= R[i] + 2)
    		return (T[i] == 1);
    	return false;
    }
    void solve()
    {
    	memset(uses, -1, sizeof(uses));
    	cin >> n >> m;
    	for(int i = 0; i < n; i++)
    		for(int j = 0; j < m; j++)
    			cin >> grid[i][j];
    	for(int i = 0;  i< n - 2; i++)
    	{
    		for(int j = 0; j < m; j++)
    		{
    			if(grid[i][j] == 'R' && grid[i + 1][j] == 'G' && grid[i + 2][j] == 'W')
    			{
    				int idx = p.size();
    				T.pb(1);
    				R.pb(i);
    				uses[i][j] = uses[i + 1][j] = uses[i + 2][j] =  idx;
    				p.pb(idx);
    				setsz.pb(1);
    			}
    		}
    	}
    	for(int i = 0; i < n; i++)
    	{
    		for(int j = 0; j < m - 2; j++)
    		{
    			if((grid[i][j] == 'R') && (grid[i][j + 1] == 'G') && (grid[i][j + 2] == 'W'))
    			{
    				int idx = p.size();
    				T.pb(0);
    				R.pb(i);
    				p.pb(idx);
    				setsz.pb(1);
    				if(uses[i][j] != -1)
    					unite(idx, uses[i][j]);
    				else
    					uses[i][j] = idx;
    				if(uses[i][j + 1] != -1)
    					unite(idx, uses[i][j + 1]);
    				else
    					uses[i][j + 1] =  idx;
    				if(uses[i][j + 2] != -1)
    					unite(idx, uses[i][j + 2]);
    				else
    					uses[i][j + 2] = idx;    				
    			}	
    		}	
    	}
    	for(int i = 0; i < (int)(p.size()); i++)
    		comp[findset(i)].pb(i);
    	//cout << p.size() << endl; 
    	seen.assign((int)(p.size()), 0);
    	int ans = 0;
    	for(int i =0; i < n; i++)
    	{
    		for(int j =0; j < m; j++)
    		{
    			if(uses[i][j] == -1)
    				continue;

    			int u = findset(uses[i][j]);
    			if(seen[u])
    				continue;
    			if(setsz[u] <= 2)
    			{
    				seen[u] = 1;
    				ans += 1;
    				continue;
    			}
     
    			sort(all(comp[u]), cmp);
    			int sz = setsz[u];
    			//cout << i << ' ' << j << ' ' << sz << endl;
    			for(int x = sz - 1; x >= 0; x--)
    			{
    				for(int b = 0; b <= 1; b++)
    				{
    					for(int bp = 0; bp <= min(x, 1); bp++)
    					{
    						for(int bpp = 0; bpp <= min(max(0,x - 1), 1); bpp++)
    						{
    								int avt = x > 1? comp[u][x - 2]: -1;
    								int prev = x > 0? comp[u][x - 1]: -1;
    								int cur = comp[u][x];
    								int nxt = x< sz - 1? comp[u][x + 1]: -1;
    								int me = (x & 1);
    								int ot = 1 - me;
    								if((b == 1 && bp == 1 && collision(cur, prev)) || (b == 1 && bpp == 1 && collision(cur, avt)))
    								{
    									dp[b][bp][bpp][me] = -MOD;
    									continue;
    								}
    								if(bp == 1 && bpp == 1 && collision(prev, avt))
    								{
    									dp[b][bp][bpp][me] = -MOD;
    									continue;
    								}
    								if(x == sz - 1)
    								{
    									dp[b][bp][bpp][me] = b;
    									continue;
    								}
    								int rep = 0;
    								if(bpp)
    								{
    									if(collision(nxt, avt))
    										rep = dp[0][b][bp][ot];
    									else
    										rep = max(dp[0][b][bp][ot], dp[1][b][bp][ot]);
    								}
    								else
    									rep = max(dp[0][b][bp][ot], dp[1][b][bp][ot]);
    								dp[b][bp][bpp][me] = b + rep;
    							
    						}
    					}
    				}
    			}
    			ans += max(dp[0][0][0][0], dp[1][0][0][0]);
    			seen[u] = 1;
    		}
    	}
    	cout << ans ;
    }
    int32_t main()
    {
    	ios::sync_with_stdio(false);
    	cin.tie(0); cout.tie(0);
    	
    	
    	int tt = 1;
    	while(tt--)
    		solve();
    }

• Subtask 1: 13 / 13
• Subtask 2: 20 / 20
• Subtask 3: 0 / 67