#include <bits/stdc++.h> #define sf scanf #define pf printf #define newl '\n' #define FAST ios_base::sync_with_stdio(0); #define Case "Case "<<++kase<<": " #define GRAY 0 #define WHITE 1 #define BLACK 2 using namespace std; int main() { int T,kase=0; cin >> T; while(T--){ int Edgdes; cin >> Edgdes; vector<int>adj[20000+1]; int color[20000+1]; memset(color,GRAY,sizeof color); for(int i=0; i<Edgdes; i++){ int u, v; cin >> u >> v; adj[u].push_back(v); adj[v].push_back(u); } int mx = 0; for(int i=0; i<20000+1; i++){ if((adj[i].size()!=0) && (color[i] == GRAY)){ int black=0,white=0; queue<int>q; q.push(i); color[i] = BLACK; black++; while(!q.empty()){ int front = q.front(); q.pop(); for(int j=0; j<adj[front].size(); j++){ if(color[adj[front][j]] == GRAY){ if(color[front] == BLACK){ color[adj[front][j]] = WHITE; white++; }else if(color[front] == WHITE){ color[adj[front][j]] = BLACK; black++; } q.push(adj[front][j]); } } } mx += max(black,white); } } cout <<Case<<mx<<newl; } return 0; }
I have stored my online judge solutions of my own :)
Tuesday, February 7, 2017
1012 - Guilty Prince - LOJ
1238 - Power Puff Girls - LOJ
#include <bits/stdc++.h> #define sf scanf #define pf printf #define newl '\n' #define FAST ios_base::sync_with_stdio(0); #define Case "Case "<<++kase<<": " #define GRAY 0 #define WHITE 1 #define BLACK 2 #define imax INT_MAX #define max3(a,b,c) max(a,max(b,c)) using namespace std; string grid[21]; int xd[]={-1,0,1,0}; int yd[]={0,1,0,-1}; bool visited[21][21]; int dist[21][21]; int row , col; int bfs(int i, int j){ pair<int,int>p; queue<pair<int,int> >q; int mx = 0; for(int i=0; i<21; i++){ for(int j=0; j<21; j++)dist[i][j]=imax; } p = {i,j}; q.push(p); dist[i][j] = 0; visited[i][j] = true; while(!q.empty()){ pair<int,int>pt; pt = q.front(); q.pop(); for(int i=0; i<4; i++){ int x = pt.first; int y = pt.second; if((x+xd[i]>=0 && x+xd[i]<row) && (y+yd[i]>=0 && y+yd[i]<col) && grid[x+xd[i]][y+yd[i]] == 'h'){ dist[x+xd[i]][y+yd[i]] = min(dist[x][y]+1, dist[x+xd[i]][y+yd[i]]); mx = max(mx, dist[x+xd[i]][ y+yd[i]]); return mx; }else{ if((x+xd[i]>=0 && x+xd[i]<row) && (y+yd[i]>=0 && y+yd[i]<col) && (grid[x+xd[i]][y+yd[i]] == '.' ||grid[x+xd[i]][y+yd[i]] == 'a'||grid[x+xd[i]][y+yd[i]] == 'b'||grid[x+xd[i]][y+yd[i]] == 'c' ) && !visited[x+xd[i]][y+yd[i]]){ dist[x+xd[i]][ y+yd[i]] = min(dist[x][y]+1, dist[x+xd[i]][y+yd[i]]); mx = max(mx, dist[x+xd[i]][ y+yd[i]]); visited[x+xd[i]][y+yd[i]] = true; q.push({x+xd[i],y+yd[i]}); } } } } return mx; } int main() { int T,kase=0; cin >> T; while(T--){ cin >> row >> col; for(int i=0; i<row; i++){ cin >> grid[i]; } int a,b,c; for(int i=0; i<row; i++){ for(int j=0; j<col; j++){ if(grid[i][j] == 'a'){ memset(visited,0,sizeof visited); memset(dist,0,sizeof dist); a = bfs(i,j); } if(grid[i][j] == 'b'){ memset(visited,0,sizeof visited); memset(dist,0,sizeof dist); b = bfs(i,j); } if(grid[i][j] == 'c'){ memset(visited,0,sizeof visited); memset(dist,0,sizeof dist); c = bfs(i,j); } } } cout<<Case<<max3(a,b,c)<<newl; } return 0; }
1009 - Back to Underworld - LOJ
#include <bits/stdc++.h> #define sf scanf #define pf printf #define newl '\n' #define FAST ios_base::sync_with_stdio(0); #define Case "Case "<<++kase<<": " #define GRAY 0 #define WHITE 1 #define BLACK 2 using namespace std; int main() { int T,kase=0; cin >> T; while(T--){ int Edgdes; cin >> Edgdes; vector<int>adj[20000+1]; int color[20000+1]; memset(color,GRAY,sizeof color); for(int i=0; i<Edgdes; i++){ int u, v; cin >> u >> v; adj[u].push_back(v); adj[v].push_back(u); } int mx = 0; for(int i=0; i<20000+1; i++){ if((adj[i].size()!=0) && (color[i] == GRAY)){ int black=0,white=0; queue<int>q; q.push(i); color[i] = BLACK; black++; while(!q.empty()){ int front = q.front(); q.pop(); for(int j=0; j<adj[front].size(); j++){ if(color[adj[front][j]] == GRAY){ //cout<<front<<' '<<adj[front][j]<<newl; if(color[front] == BLACK){ color[adj[front][j]] = WHITE; white++; }else if(color[front] == WHITE){ color[adj[front][j]] = BLACK; black++; } // cout<<black<<' '<<white<<newl; q.push(adj[front][j]); } } } mx += max(black,white); } } cout <<Case<<mx<<newl; } return 0; }
Tuesday, January 10, 2017
1003 - Drunk - LightOJ
#include <bits/stdc++.h> #define sf scanf #define pf printf #define WHITE 0 #define GRAY 1 #define BLACK 2 #define newl '\n' #define FAST ios_base::sync_with_stdio(0); using namespace std; map<string , int>visited; map<string, vector<string> >mp; bool cycle; void visit(string start){ visited[start] = GRAY; for(int i=0; i<mp[start].size(); i++){ if(visited[mp[start][i]] == WHITE){ visit(mp[start][i]); }else if(visited[mp[start][i]] == GRAY){ cycle = true; return; } } visited[start] = BLACK; } void DFS(){ map<string, vector<string> >::iterator it; visited.clear(); for(it = mp.begin() ; it!=mp.end(); it++){ if(cycle)return; if(visited[(*it).first] == WHITE){ visit((*it).first); } } } int main() { FAST; int t , kase=0; cin >> t; while(t--){ int n; cin >> n; for(int i=0; i<n; i++){ string a , b; cin >> a >> b; mp[a].push_back(b); visited[a] = WHITE; } cycle = false; DFS(); if(cycle)cout<<"Case "<<++kase<<": No"<<newl; else cout<<"Case "<<++kase<<": Yes"<<newl; mp.clear(); visited.clear(); } return 0; }
Subscribe to:
Posts (Atom)