oj.uz

Submission #786635

# Submission time Handle Problem Language Result Execution time Memory
786635 2023-07-18T10:34:44 Z allin27x Tropical Garden (IOI11_garden) C++17
0 / 100
 1 ms 468 KB 
#include <bits/stdc++.h>
using namespace std;


int gl;
int ps[(int)15e4+2][2];
int vis[(int)15e4+2][2];
int ds[(int)15e4+2][2];
int gd[(int)15e4+2][2];

int a1 = 0; int a2 = 0;
int g1 = 0; int g2 = 0;
int dfs1(int p, int last, int len){
	int nx;
	if (last == ps[p][0]) nx = 1;
	else nx = 0;

	if (p==gl) return len * (2*nx-1);
	if (vis[p][nx]) return (int)1e7;
	vis[p][nx] = 1;
	dfs1(ps[p][nx], p, len+1);
}


void answer(int x);


void dfs2(int p, int last){
	int nx;  if (last == ps[p][0]) nx = 1; else nx = 0;
	if (p == gl){
		gd[p][nx] = nx;
		ds[p][nx] = 0;
		return;
	}
	if (ds[p][nx]) return;
	if (vis[p][nx]){
		ds[p][nx] = (int)-1e5;
		return;
	}
	vis[p][nx] = 1;
	int nxt = ps[p][nx];
	int d; if (p == ps[nxt][0]) d = 1; else d = 0;
	dfs2(nxt, p);
	gd[p][nx] = gd[nxt][d];
	ds[p][nx] = ds[nxt][d]+1;
}


void count_routes(int N, int M, int P, int R[][2], int Q, int G[]){ 
	gl = P;
    for (int i=0; i<N; i++) ps[i][0]=-1, ps[i][1]=-1;
    for (int i=0; i<M; i++){
        int a = R[i][0]; int b= R[i][1];
        if (ps[a][0]==-1) ps[a][0] = b; else if (ps[a][1]==-1) ps[a][1] = b;
        if (ps[b][0]==-1) ps[b][0] = a; else if (ps[b][1]==-1) ps[b][1] = a;
    }
    for (int i=0; i<N; i++) if (ps[i][1]==-1) ps[i][1] = ps[i][0];
    
    for (int i=0; i<N; i++) vis[i][0] = 0, vis[i][1] = 0;
    int r1 = dfs1(ps[P][0], P, 1);
	for (int i=0; i<N; i++) vis[i][0] = 0, vis[i][1] = 0;
	int r2 = dfs1(ps[P][1], P, 1);
	if (r1!=1e7) {
		if (r1>0) g1 = 1;
		a1 = abs(r1);
	}
	if (r2!=1e7){
		if (r2>0) g2 = 1;
		a2 = abs(r2);
	}
	for (int i=0; i<N; i++) vis[i][0] = 0, vis[i][1] = 0;
    for (int i=0; i<N; i++) ds[i][0] = 0, ds[i][1] = 0;
    for (int i=0; i<N; i++) {
    	if (i==P) continue;
    	if (!ds[i][0]) dfs2(i, -1);
    }

    for (int q = 0; q<Q; q++){
    	int k = G[q];
    	int ans = 0;
    	for (int i=0; i<N; i++){
    		if (ds[i][0] < 0) continue;
    		if (k<ds[i][0]) continue;
    		int t= k - ds[i][0];
    		if (gd[i][0]==0){
    			if (a1 == 0) continue;
    			if (g1 == 0 && t%a1 == 0) ans++;
    			if (g1 == 1 && a2 == 0 && (t==0 || t==a1)) ans++;
    			if (g1 == 1 && g2 == 0 && (t%(a1+a2)==0 || t%(a1+a2)==a1)) ans++;
				if (g1 == 1 && g2 == 1 && (t==0 || (t-a1)&a2 == 0)) ans++;    			 
    		} else {
    			swap(a1,a2); swap(g1,g2);
    			if (a1 == 0) continue;
    			if (g1 == 0 && t%a1 == 0) ans++;
    			if (g1 == 1 && a2 == 0 && (t==0 || t==a1)) ans++;
    			if (g1 == 1 && g2 == 0 && (t%(a1+a2)==0 || t%(a1+a2)==a1)) ans++;
				if (g1 == 1 && g2 == 1 && (t==0 || (t-a1)&a2 == 0)) ans++;    			 
    			swap(a1,a2); swap(g1,g2);
    		}
    	}
    	answer(ans);
    }
}

Compilation message

garden.cpp: In function 'void count_routes(int, int, int, int (*)[2], int, int*)':
garden.cpp:90:50: warning: suggest parentheses around comparison in operand of '&' [-Wparentheses]
   90 |     if (g1 == 1 && g2 == 1 && (t==0 || (t-a1)&a2 == 0)) ans++;
      |                                               ~~~^~~~
garden.cpp:97:50: warning: suggest parentheses around comparison in operand of '&' [-Wparentheses]
   97 |     if (g1 == 1 && g2 == 1 && (t==0 || (t-a1)&a2 == 0)) ans++;
      |                                               ~~~^~~~
garden.cpp: In function 'int dfs1(int, int, int)':
garden.cpp:21:6: warning: control reaches end of non-void function [-Wreturn-type]
   21 |  dfs1(ps[p][nx], p, len+1);
      |  ~~~~^~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 49.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 468 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 468 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
0 / 31.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 468 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -