Submission #240897

#TimeUsernameProblemLanguageResultExecution timeMemory
240897aggu_01000101Dango Maker (JOI18_dango_maker)C++14
100 / 100
1037 ms182072 KiB
#include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> #define INF 100000000000000000 //#define int long long #define lchild(i) (i*2 + 1) #define rchild(i) (i*2 + 2) #define mid(l, u) ((l+u)/2) #define x(p) p.first #define y(p) p.second #define MOD 998244353 #define ordered_set tree<pair<int, int>, null_type,less<pair<int, int>>, rb_tree_tag,tree_order_statistics_node_update> using namespace std; struct node{ char c; int first, second; }; int n, m; const int N = 3000;//first->horizontal, second -> vertical vector<bool> vis; int currnode = 0; node mat[N][N]; vector<pair<int, int>> nv; int solve(int i){ int type = 1; if(mat[nv[i].first][nv[i].second].first != i){ type = 0; } //cout<<i<<" "<<type<<endl; vector<int> lvls; queue<pair<pair<int, int>, int>> q; q.push({{i, type}, 0}); vis[i] = true; while(!q.empty()){ pair<pair<int, int>, int> curr = q.front(); q.pop(); if(lvls.size()<=curr.second) lvls.push_back(1); else lvls[curr.second]++; if(curr.first.second == 0){ int i = nv[curr.first.first].first; int j = nv[curr.first.first].second; if(mat[i][j].first != -1){ if(!vis[mat[i][j].first]){ vis[mat[i][j].first] = true; q.push({{mat[i][j].first, 1}, curr.second+1}); } } if(j>0 && mat[i+1][j-1].first!=-1){ if(!vis[mat[i+1][j-1].first]){ vis[mat[i+1][j-1].first] = true; q.push({{mat[i+1][j-1].first, 1}, curr.second+1}); } } if(j>1 && mat[i+2][j-2].first!=-1){ if(!vis[mat[i+2][j-2].first]){ vis[mat[i+2][j-2].first] = true; q.push({{mat[i+2][j-2].first, 1}, curr.second+1}); } } } else{ int i = nv[curr.first.first].first; int j = nv[curr.first.first].second; if(mat[i][j].second != -1){ if(!vis[mat[i][j].second]){ vis[mat[i][j].second] = true; q.push({{mat[i][j].second, 0}, curr.second+1}); } } if(i>0 && mat[i-1][j+1].second!=-1){ if(!vis[mat[i-1][j+1].second]){ vis[mat[i-1][j+1].second] = true; q.push({{mat[i-1][j+1].second, 0}, curr.second+1}); } } if(i>1 && mat[i-2][j+2].second!=-1){ if(!vis[mat[i-2][j+2].second]){ vis[mat[i-2][j+2].second] = true; q.push({{mat[i-2][j+2].second, 0}, curr.second+1}); } } } } if(lvls.size()==1) return lvls[0]; if(lvls.size()==2) return max(lvls[0], lvls[1]); pair<int, int> dp = {lvls[0], lvls[1]}; int tr = max(dp.first, dp.second); for(int i = 2;i<lvls.size();i++){ int temp = max(dp.first + lvls[i], dp.second); dp.first = dp.second; dp.second = temp; tr = max(tr, temp); } return tr; } signed main(){ ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); cin>>n>>m; for(int i = 0;i<n;i++){ string s; for(int j = 0;j<m;j++) cin>>mat[i][j].c; } for(int i = 0;i<n;i++){ for(int j = 0;j<m;j++) mat[i][j].first = mat[i][j].second = -1; } for(int i = 0;i<n;i++){ for(int j = 0;j<m;j++){ if(mat[i][j].c!='R') continue; if(i+2<n){ if(mat[i+1][j].c=='G' && mat[i+2][j].c=='W'){ int cnode = currnode++; vis.push_back(false); nv.push_back({i, j}); mat[i][j].second = cnode; } } if(j+2<m){ if(mat[i][j+1].c=='G' && mat[i][j+2].c=='W'){ int cnode = currnode++; vis.push_back(false); nv.push_back({i, j}); mat[i][j].first = cnode; } } } } int ans = 0; for(int i = 0;i<currnode;i++){ /*cout<<i<<" is connected to: "; for(int j: adj[i]){ cout<<j<<" "; } cout<<endl; */ if(!vis[i]){ ans+=solve(i); } } cout<<ans<<endl; //create a node out of each skewer that you can make //connect nodes that intersect with each other //For each connected component, } /* 4 4 RGWR GRRG WGGW WWWR 5 5 RGRGW GRRGW WGGWR RWRGW RGWGW */

Compilation message (stderr)

dango_maker.cpp: In function 'int solve(int)':
dango_maker.cpp:37:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if(lvls.size()<=curr.second) lvls.push_back(1);
            ~~~~~~~~~~~^~~~~~~~~~~~~
dango_maker.cpp:88:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 2;i<lvls.size();i++){
                   ~^~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...