oj.uz

Submission #786685

# Submission time Handle Problem Language Result Execution time Memory
786685 2023-07-18T11:15:25 Z allin27x Tropical Garden (IOI11_garden) C++17
69 / 100
 2156 ms 7580 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;
	return dfs1(ps[p][nx], p, len+1);
}


void answer(int x);


// void answer(int x){
//     cout<<x<<'\n';
// }

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 || (i==P && g1==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 (t && t<a1) continue;
				if (g1 == 1 && g2 == 1 && (t==0 || (t-a1)%a2 == 0)) ans++;    			 
    		} else {
    			if (a2 == 0) continue;
    			if (g2 == 1 && t%a2 == 0) ans++;
    			if (g2 == 0 && a1 == 0 && (t==0 || t==a2)) ans++;
    			if (g2 == 0 && g1 == 1 && (t%(a1+a2)==0 || t%(a1+a2)==a2)) ans++;
				if (t && t<a2) continue;
				if (g2 == 0 && g1 == 0 && (t==0 || (t-a2)%a1 == 0)) ans++; 
       		}
    	}
    	answer(ans);
    }
}

// int main(){
//     // int n = 5; int m = 5;
//     // int p=2;int q = 2; int g[] = {3,1};
//     // int r[][2]= {
//     //     {1,0},
//     //     {1,2},
//     //     {3,2},
//     //     {1,3},
//     //     {4,2}
//     // };

//     // count_routes(n,m,p,r,q,g);
//     // int n = 6; int m = 6;
//     // int p=0;int q = 1; int g[] = {3};
//     // int r[][2]= {
//     //     {1,2},
//     //     {0,1},
//     //     {0,3},
//     //     {3,4},
//     //     {4,5},
//     //     {1,5}
//     // };

//     // count_routes(n,m,p,r,q,g);
//     int n = 5; int m = 4;
//     int p=0;int q = 10; int g[] = {100,101,102,103,104,105,106,107,108,109};
//     int r[][2]= {
//         {0,1},
//         {1,2},
//         {2,3},
//         {3,4}
//     };

//     count_routes(n,m,p,r,q,g);
//     // cout<<'\n';
//     // for (int i=0; i<n; i++){
//     //     cout<<i<<' '<<jump(i, 4)<<'\n';
//     // }
// }

Subtask #1
49.0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 468 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 468 KB Output is correct
10 Correct 1 ms 312 KB Output is correct
11 Correct 4 ms 1620 KB Output is correct
12 Correct 9 ms 2620 KB Output is correct
13 Correct 16 ms 4300 KB Output is correct
14 Correct 25 ms 6324 KB Output is correct
15 Correct 27 ms 6452 KB Output is correct
16 Correct 23 ms 5052 KB Output is correct
17 Correct 22 ms 4564 KB Output is correct
18 Correct 9 ms 2516 KB Output is correct
19 Correct 25 ms 6420 KB Output is correct
20 Correct 27 ms 6404 KB Output is correct
21 Correct 24 ms 4992 KB Output is correct
22 Correct 24 ms 4492 KB Output is correct
23 Correct 27 ms 7136 KB Output is correct

Subtask #3
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 468 KB Output is correct
10 Correct 1 ms 312 KB Output is correct
11 Correct 4 ms 1620 KB Output is correct
12 Correct 9 ms 2620 KB Output is correct
13 Correct 16 ms 4300 KB Output is correct
14 Correct 25 ms 6324 KB Output is correct
15 Correct 27 ms 6452 KB Output is correct
16 Correct 23 ms 5052 KB Output is correct
17 Correct 22 ms 4564 KB Output is correct
18 Correct 9 ms 2516 KB Output is correct
19 Correct 25 ms 6420 KB Output is correct
20 Correct 27 ms 6404 KB Output is correct
21 Correct 24 ms 4992 KB Output is correct
22 Correct 24 ms 4492 KB Output is correct
23 Correct 27 ms 7136 KB Output is correct
24 Correct 1 ms 340 KB Output is correct
25 Correct 39 ms 1716 KB Output is correct
26 Correct 52 ms 2712 KB Output is correct
27 Correct 1018 ms 4656 KB Output is correct
28 Correct 613 ms 7352 KB Output is correct
29 Correct 2156 ms 7580 KB Output is correct
30 Correct 1254 ms 6008 KB Output is correct
31 Correct 1220 ms 5452 KB Output is correct
32 Incorrect 59 ms 2492 KB Output isn't correct
33 Halted 0 ms 0 KB -