numberslayer's blog

By numberslayer, history, 7 days ago, In English,

i was trying the question 839C - Journey in python3 and wrote a recursive program when i submitted it,it gave runtime error i tried changing recursion depth(although when i saw the test cases it passed a case with n=100000 and gave RE on n=90000) . it still didn't work then i wrote the same code in cpp and it got accepted . the same thing also happened on 580C - Kefa and Park where there was some problem with recursion not working properly .can anybody tell what is going wrong.

python code for Journey 88623570

import math
import time
from collections import defaultdict,deque
from sys import stdin,stdout
from bisect import bisect_left,bisect_right
from queue import PriorityQueue 
import sys
sys.setrecursionlimit(10**5)
def find(curr,parent,prob,plen):
    leaf=True
    for i in graph[curr]:
        if(i!=parent):
            if(curr!=1):
                find(i,curr,prob/(len(graph[curr])-1),plen+1)
            else:
                find(i,curr,prob/(len(graph[curr])),plen+1)
            leaf=False
    if(leaf):
        ans[0]+=prob*plen
n=int(stdin.readline())
graph=defaultdict(lambda:[])
for i in range(n-1):
    u,v=map(int,stdin.readline().split())
    graph[u].append(v)
    graph[v].append(u)
ans=[0]
find(1,-1,1,0)
print(ans[0])

cpp code(Working) for Journey 88623478

using namespace std;
const long long A = 100000000000000LL, N = 10e5 +10;

vector<long long> a[N];
long long c[N], x, y, i, j, n, m;
double o = 0.0;

void go(int v, int pr, double prob, int len)
{
	bool leaf = 1;
	for (int i = 0; i < a[v].size(); i++)
		if (a[v][i] != pr)
		{
			leaf = 0;
			if (v != 0)
				go(a[v][i], v, prob / double(a[v].size() &mdash; 1), len + 1);
			else
				go(a[v][i], v, prob / double(a[v].size()), len + 1);
		}
	if (leaf)
		o += prob * len;
}

int main()
{
	cin >> n;
	for (i = 0; i < n &mdash; 1; i++)
	{
		scanf("%d%d", &x, &y), x--, y--, a[x].pb(y), a[y].pb(x);
	}
	go(0, -1, 1.0, 0);
	cout << fixed << setprecision(9) << o << "\n";
}

python code for Kefa and Park 88620540

import sys
final=[0]
sys.setrecursionlimit(100010)
def find(curr,parent,cats):
    if(cats>m):
        return 
    ok=1
    for i in graph[curr]:
        if(i!=parent):
            ok=0
            find(i,curr,cats*a[i]+a[i])
    final[0]+=ok
n,m=map(int,stdin.readline().split())
a=list(map(int,stdin.readline().split()))
graph=defaultdict(lambda:[])
for _ in range(n-1):
    x,y=map(int,stdin.readline().split())
    x-=1
    y-=1
    graph[x].append(y)
    graph[y].append(x)
find(0,-1,a[0])
print(final[0])

cpp code(Working) for Kefa and Park 88620695

using namespace std;
const long long A=100000000000000LL,N=228228;
 
vector<long long> a[N];
long long c[N],o,x,y,i,j,n,m;
 
void go(int v,int pr,int k){
	if(k>m)return;
	int ok=1;
	for(int i=0;i<a[v].size();i++)if(a[v][i]!=pr)ok=0,go(a[v][i],v,k*c[a[v][i]]+c[a[v][i]]);
	o+=ok;
}
 
int main(){
	cin>>n>>m;
	for(i=0;i<n;i++)scanf("%d",&c[i]);
	for(i=1;i<n;i++)scanf("%d%d",&x,&y),x--,y--,a[x].pb(y),a[y].pb(x);
	go(0,-1,c[0]);
	cout<<o<<"\n";
}
 
 
 
 
  • Vote: I like it
  • 0
  • Vote: I do not like it

»
7 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by numberslayer (previous revision, new revision, compare).

»
6 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by numberslayer (previous revision, new revision, compare).

»
6 days ago, # |
  Vote: I like it +9 Vote: I do not like it

yeah the same kind of problem happened with my friend, we were solving some recursive problem, then c++ worked fine, but at that time python gave him runtime error. I suggest him to use setRecursionLimit() function, but that did not work.