License Plate Recognition

#include <bits/stdc++.h>
using namespace std;

int T;
char s[35][105];
int cnt[105];
int ansl[10],ansr[10];

int main(){
    scanf("%d",&T);
    for (int tt=1;tt<=T;tt++){
        memset(cnt,0,sizeof(cnt));
        for (int i=1;i<=30;i++){
            scanf("%s",s[i]+1);
            for (int j=1;j<=100;j++){
                if (s[i][j]=='#') cnt[j]++;
            }
        }
        int pos=100;
        for (int i=7;i>=2;i--){
            while (pos>=1 && !cnt[pos]) pos--;
            ansr[i]=pos;
            while (pos>=1 && cnt[pos]) pos--;
            ansl[i]=pos+1;
        }
        while (pos>=1 && !cnt[pos]) pos--;
        ansr[1]=pos;
        pos=1;
        while (pos<=100 && !cnt[pos]) pos++;
        ansl[1]=pos;
        printf("Case #%d:\n",tt);
        for (int i=1;i<=7;i++){
            printf("%d %d\n",ansl[i],ansr[i]);
        }
    }
    return 0;
}

Kanade Loves Maze Designing

#include<iostream>
#include<cstring>
#include<queue>
#include<map>
#include<set>
#include<algorithm>
#include<cmath>
#include<vector>

#define fi first
#define se second

using namespace std;

typedef long long ll;
typedef pair<int,int> pii;

const int inf=0x3f3f3f3f;
const double eps=1e-8;

const int N=100010;
const int mod1=1e9+7;
const int mod2=1e9+9;
const int val=19560929;

int T;
int n;
int col[N],f[N];
ll _x1[N],_x2[N];
int cnt[N];
ll ans1,ans2,ans=0;

int h[N],e[N<<1],ne[N<<1],idx;

void add(int a,int b){
    e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}

void ADD(int x){
    if(cnt[x]==0)    ans++;
    cnt[x]++;
}

void DEL(int x){
    if(cnt[x]==1)    ans--;
    cnt[x]--;
}

void init(){
    _x1[0]=1;
    _x2[0]=1;
    for(int i=1;i<=2000;i++){
        _x1[i]=1ll*val*_x1[i-1]%mod1;
        _x2[i]=1ll*val*_x2[i-1]%mod2;
    }
}

void dfs(int x,int fa){
    ADD(col[x]);
    f[x]=ans;
    for(int i=h[x];i!=-1;i=ne[i]){
        int y=e[i];
        if(y==fa)    continue;
        dfs(y,x);
    }
    DEL(col[x]);
}

int main(){
    cin.tie(0);
    cout.tie(0);
    cin>>T;
    init();
    while(T--){
        cin>>n;
        for(int i=1;i<=n;i++)    h[i]=-1;
        for(int i=2;i<=n;i++){
            int p;
            cin>>p;
            add(i,p);
            add(p,i);
        }
        for(int i=1;i<=n;i++)    cin>>col[i];
        for(int i=1;i<=n;i++){
            dfs(i,-1);
            ans1=0,ans2=0;
            for(int j=1;j<=n;j++){
                ans1=(ans1+1ll*f[j]*_x1[j-1]%mod1)%mod1;
                ans2=(ans2+1ll*f[j]*_x2[j-1]%mod2)%mod2;
            }
            cout<<ans1<<" "<<ans2<<endl;
        }
    }
}