티스토리 뷰
#include <bits/stdc++.h>
using namespace std;
int n;
int a[257][257];
int b[257][257][9][9];
int c[257][257][9][9];
pair<int,int> aa[256*256+1];
int mix[256*256+1][17];
int miy[256*256+1][17];
int mxx[256*256+1][17];
int mxy[256*256+1][17];
int p[256*256+1];
inline int f(int x,int y,int xx,int yy){
int k=p[xx-x+1];
int t=p[yy-y+1];
int kk=xx-(1<<k)+1;
int tt=yy-(1<<t)+1;
return min({b[x][y][k][t],b[kk][y][k][t],b[x][tt][k][t],b[kk][tt][k][t]});
}
inline int g(int x,int y,int xx,int yy){
int k=p[xx-x];
int t=p[yy-y];
int kk=xx-(1<<k)+1;
int tt=yy-(1<<t)+1;
return max({c[x][y][k][t],c[kk][y][k][t],c[x][tt][k][t],c[kk][tt][k][t]});
}
inline int fx(int l,int r){
int k=p[r-l+1];
int kk=r-(1<<k)+1;
return min(mix[l][k],mix[kk][k]);
}
inline int fy(int l,int r){
int k=p[r-l+1];
int kk=r-(1<<k)+1;
return min(miy[l][k],miy[kk][k]);
}
inline int gx(int l,int r){
int k=p[r-l+1];
int kk=r-(1<<k)+1;
return max(mxx[l][k],mxx[kk][k]);
}
inline int gy(int l,int r){
int k=p[r-l+1];
int kk=r-(1<<k)+1;
return max(mxy[l][k],mxy[kk][k]);
}
void solve(int tc){
cin>>n;
for(int i=1 ; i<=n ; i++){
for(int j=1 ; j<=n ; j++){
cin>>a[i][j];
b[i][j][0][0]=c[i][j][0][0]=a[i][j];
mix[a[i][j]][0]=mxx[a[i][j]][0]=i;
miy[a[i][j]][0]=mxy[a[i][j]][0]=j;
}
}
int j=0;
for(int i=1 ; i<=n*n ; i++){
if(i==(1<<(j+1)))j++;
p[i]=j;
}
for(int i=1 ; i<=16 ; i++){
for(int j=1 ; j<=n*n ; j++){
int r=min(n*n,j+(1<<(i-1)));
mix[j][i]=min(mix[j][i-1],mix[r][i-1]);
mxx[j][i]=max(mxx[j][i-1],mxx[r][i-1]);
miy[j][i]=min(miy[j][i-1],miy[r][i-1]);
mxy[j][i]=max(mxy[j][i-1],mxy[r][i-1]);
}
}
for(int x=0 ; x<=8 ; x++){
for(int y=0 ; y<=8 ; y++){
for(int i=1 ; i<=n ; i++){
for(int j=1 ; j<=n ; j++){
if(y==0 && x==0)continue;
if(y==0){
int r=(1<<(x-1));
b[i][j][x][0]=min(b[i][j][x-1][0],b[min(n,i+r)][j][x-1][0]);
c[i][j][x][0]=max(c[i][j][x-1][0],c[min(n,i+r)][j][x-1][0]);
continue;
}
int r=(1<<(y-1));
b[i][j][x][y]=min(b[i][j][x][y-1],b[i][min(n,j+r)][x][y-1]);
c[i][j][x][y]=max(c[i][j][x][y-1],c[i][min(n,j+r)][x][y-1]);
}
}
}
}
int ans=0;
for(int i=1 ; i<=n*n ; i++){
ans++;
int j=i+1;
while(j<=n*n){
int k=j-i+1;
int kk=p[k];
int xx=fx(i,j);
int xxx=gx(i,j);
int yy=fy(i,j);
int yyy=gy(i,j);
int miv=f(xx,yy,xxx,yyy);
int mxv=g(xx,yy,xxx,yyy);
if(miv<i)break;
if(mxv-miv+1==(xxx-xx+1)*(yyy-yy+1)){
ans++;
j=mxv+1;
}
else if(mxv>j)j=mxv;
else j++;
}
}
cout<<"Case #"<<tc<<"\n"<<ans<<"\n";
}
int main(){
cin.tie(0);
ios_base::sync_with_stdio(0);
int tc;
cin>>tc;
for(int i=1 ; i<=tc ; i++)solve(i);
return 0;
}773점을 받았다.
3,4번 코드만 잃어버릴까봐 올려놓는다.
#include <bits/stdc++.h>
using namespace std;
//출처: http://boj.kr/1f1032aede1a45159e79d4c90800bc6c
int n,m,k;
const int MX=1e5+5;
const int MAXN=3*MX;
vector<vector<int>> SCC;
int num[MAXN], low[MAXN], sn[MAXN];
bool chk[MAXN];
stack<int> st;
int vis3[MX*3][3];
vector<pair<int,int>> a[3*MX];
int dp[3*MX];
int dy[3*MX][3];
int deg[3*MX];
int vis[3*MX];
int vis2[3*MX];
int ans;
int flag;
int cnt, SN;
void dfs2(int n){
chk[n] = 1;
st.push(n);
num[n] = ++cnt;
low[n] = cnt;
for (auto x : a[n]){
int next=x.first;
if (num[next] == 0){
dfs2(next);
low[n] = min(low[n], low[next]);
}
else if (chk[next])
low[n] = min(low[n], num[next]);
}
if (num[n] == low[n]){
vector<int> scc;
while (!st.empty()){
int x = st.top();
st.pop();
sn[x] = SN;
chk[x] = 0;
scc.push_back(x);
if (n == x)
break;
}
SCC.push_back(scc);
SN++;
}
}
void f(int v,int x){
vis3[v][x]=1;
for(auto xx: a[v]){
int u=xx.first;
int y=xx.second;
if(y==1){
if(vis3[u][x]==0)
f(u,x);
dy[v][x]=max(dy[v][x],dy[u][x]+1);
}
else{
if(x==0)continue;
if(vis3[u][x-1]==0)
f(u,x-1);
dy[v][x]=max(dy[v][x],dy[u][x-1]);
}
}
}/*
void f(int v){
vis[v]=1;
dp[v]=0;
for(auto x: a[v]){
int u=x.first;
int y=x.second;
if(y==0)continue;
if(vis[u]==0)f(u);
dp[v]=max(dp[u]+y,dp[v]);
//cout<<v<<" "<<u<<" "<<dp[u]<<endl;
}
}*/
void dfs(int v){
vis[v]=vis2[v]=1;
for(auto x: a[v]){
if(x.second==0)continue;
int u=x.first;
if(vis[u]){
flag=1;
return;
}
if(!vis2[u]){
dfs(u);
}
}
vis[v]=0;
}
void solve(int tc){
cin>>n>>m>>k;
for(int i=1 ; i<=3*n ; i++){
a[i].clear();
vis3[i][0]=vis3[i][1]=vis3[i][2]=0;
vis2[i]=vis[i]=0;
deg[i]=0;
dp[i]=0;
dy[i][0]=dy[i][1]=dy[i][2]=0;
}
for(int i=0 ; i<m ; i++){
int u,v;
char c;
cin>>u>>v>>c;
if(c=='A'){
a[3*u].push_back({v*3-2,1});
for(int j=0 ; j<3 ; j++){
int q=3*u-j;
int w=3*v-j;
a[q].push_back({w,0});
}
}
if(c=='B'){
a[3*u-2].push_back({v*3-1,1});
for(int j=0 ; j<3 ; j++){
int q=3*u-j;
int w=3*v-j;
a[q].push_back({w,0});
}
}
if(c=='C'){
a[3*u-1].push_back({v*3,1});
for(int j=0 ; j<3 ; j++){
int q=3*u-j;
int w=3*v-j;
a[q].push_back({w,0});
}
}
}
if(k>=0){
flag=0;
ans=0;
for(int i=1 ; i<=3*n ; i++){
if(!vis2[i])dfs(i);
}
if(flag){
cout<<"Case #"<<tc<<endl<<-1<<endl;
return;
}
for(int i=1 ; i<=3*n ; i++){
for(int j=0 ; j<=k ; j++){
if(vis3[i][j]==0){
f(i,j);
ans=max(ans,dy[i][j]);
}
}
}
cout<<"Case #"<<tc<<endl<<ans<<endl;
return;
}
cnt=0;
SCC.clear();
SN=0;
ans=0;
for(int i=1 ; i<=n*3 ; i++){
low[i]=num[i]=sn[i]=chk[i]=0;
}
for(int i=1 ; i<=3*n ; i++){
if(!num[i])dfs2(i);
}
for(int i=0; i<SN ; i++)
{
int k=0;
for(auto x: SCC[i]){
int y=x%3;
k|=(1<<y);
}
if(k==7){
cout<<"Case #"<<tc<<endl<<-1<<endl;
return;
}
dp[i]=__builtin_popcount(k)-1;
for(auto x: SCC[i]){
for(auto y: a[x]){
int u=y.first;
int z=y.second;
if(sn[u]!=i)
dp[i]=max(dp[i],__builtin_popcount(k)-1+z+dp[sn[u]]);
}
}
ans=max(ans,dp[i]);
}
cout<<"Case #"<<tc<<endl<<ans<<endl;
}
int main(){
cin.tie(0);
ios_base::sync_with_stdio(0);
int tc;
cin>>tc;
for(int i=1 ; i<=tc ; i++)solve(i);
return 0;
}
'알고리즘,PS' 카테고리의 다른 글
| 2023 고연전 프로그래밍 경진대회 후기 (0) | 2023.04.03 |
|---|---|
| 2022 ICPC Seoul Regional 후기 (2) | 2022.11.21 |
| 2022.07.11 팀연습 기록 (0) | 2022.07.14 |
| 2022.07.04 팀연습 기록 (0) | 2022.07.04 |
| 2022 UCPC 인터넷 예선 후기 (0) | 2022.07.03 |
댓글