Google APAC 2015 University Graduates Test Round D

RoundD_A.cpp

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

int s;
bool inmap(int i,int j,int s){
	if( i < 0 || j < 0 || i >= s || j >= s){
		return false;
	}
	else{
		return true;
	}
}

int m[1500][1500];
int vis[1500][1500];

int dir[5][3] = {{0,1},{0,-1},{1,0},{-1,0}};

int dfs(int i, int j){
	int flag = 1;
	int tmp;
	for(int k = 0; k < 4; k++){
		if( inmap((i+dir[k][0]),(j+dir[k][1]),s) && 
			(m[i+dir[k][0]][j+dir[k][1]] - m[i][j]) == 1){
				tmp = dfs(i+dir[k][0],j+dir[k][1]);
				return tmp + 1;
				flag = 0;
		}
	}
	if(flag){
		return 0;
	}
}

int main(){
	ios_base::sync_with_stdio(0);
	int T;
	int kase = 1;
	cin >> T;
	while(T--){
		int res = -1;
		int tmp;
		int sres = s*s + 10;
		cin >> s;
		for(int i = 0; i < s; i++){
			for(int j = 0; j < s; j++){
				cin >> m[i][j];
				//vis[i][j] = 0;
			}
		}
		for(int i = 0; i < s; i++){
			for(int j= 0 ;j < s; j++){
				// if (vis[i][j] == 0){
				// 	vis[i][j] = 1;
					tmp = dfs(i,j);
					if ( tmp + 1 == res){
						if ( m[i][j] < sres){
							sres = m[i][j];
						}
					}
					else if (tmp + 1 > res){
						res = tmp + 1;
						sres = m[i][j];
					}
					
				// }
			}
		}
		printf("Case #%d: %d %d\n", kase++, sres, res);
	}
}

RoundD_B.cpp

#include <bits/stdc++.h> 
using namespace std;    
     
#define lson l , m , rt << 1    
#define rson m + 1 , r , rt << 1 | 1   
#define root 1 , N , 1   
#define LL long long    
const int maxn = 111111;    
LL add[maxn<<2];    
LL sum[maxn<<2];    
void PushUp(int rt) {    
    sum[rt] = sum[rt<<1] + sum[rt<<1|1];    
}    
void PushDown(int rt,int m) {    
    if (add[rt]) {    
        add[rt<<1] += add[rt];    
        add[rt<<1|1] += add[rt];    
        sum[rt<<1] += add[rt] * (m - (m >> 1));    
        sum[rt<<1|1] += add[rt] * (m >> 1);    
        add[rt] = 0;    
    }    
}    
void build(int l,int r,int rt) {    
    add[rt] = 0;    
    if (l == r) {
        sum[rt] = 0;
        return ;    
    }    
    int m = (l + r) >> 1;    
    build(lson);    
    build(rson);    
    PushUp(rt);    
}    
void update(int L,int R,int c,int l,int r,int rt) {    
    if (L <= l && r <= R) {    
        add[rt] += c;    
        sum[rt] += (LL)c * (r - l + 1);    
        return ;    
    }    
    PushDown(rt , r - l + 1);    
    int m = (l + r) >> 1;    
    if (L <= m) update(L , R , c , lson);    
    if (m < R) update(L , R , c , rson);    
    PushUp(rt);    
}    
LL query(int L,int R,int l,int r,int rt) {    
    if (L <= l && r <= R) {    
        return sum[rt];    
    }    
    PushDown(rt , r - l + 1);    
    int m = (l + r) >> 1;    
    LL ret = 0;    
    if (L <= m) ret += query(L , R , lson);    
    if (m < R) ret += query(L , R , rson);    
    return ret;    
}

int main() {
    int T;
    int kase = 1;
    cin >> T;
    //cout << T << endl;
    while(T--){
        int a,b;
        int N;
        N = 6000;
        build(root);         
        int ud;
        scanf("%d",&ud);
        int Bus[1500];
        //cout << ud << endl;
        for(int i = 0; i < ud*2; i++){
            cin >> a;
            Bus[i] = a;
            //cout << a << " ";
        }
        for(int i = 0; i < ud*2; i = i + 2){
            update(Bus[i] , Bus[i+1] , 1 , root);
        }
        int chaxun;
        scanf("%d",&chaxun);
        cout << "Case #" << kase++ << ": " ;  
        for(int i = 0; i < chaxun; i++){
                scanf("%d",&a);   
                printf("%d ",query(a , a ,root));
        }    
        printf("\n");
    }
    return 0;    
}    

RoundD_C.py

T = input()
kase = 1
while T:
	m = {}
	line = []
	T -= 1
	n = input()
	for i in range(0,n):
		sour = raw_input()
		dest = raw_input()
		m[sour] = dest
	
	for key in m:
		cnt = 0
		res = key
		t = m[key]
		line = []
		line.append((key,t))
		while t in m:
			cnt += 1
			line.append((t,m[t]))
			t = m[t]
			
		if cnt == n - 1:
			print "Case #%d:" % kase,
			for i in line:
				print "%s-%s" % ( i[0],i[1] ),
			print ""

	kase += 1