소프티어

반례를 못찾겠어요ㅠㅠ

처음에 각 리프노드까지의 경로에 대해서 행복값 찾는 코드로는 타임아웃나는 테스트 케이스가 하나 있어서 여기저기 참고해서 코드를 고쳐봤는데요. 각 단계에서 dp 를 계산하고 다음으로 넘기는 방식을 고안해 봤는데 기본으로 주어지는 테스트케이스는 성공하는데 나머지는 다 실패하는거 같아요. 제가 이런 저런 테스트 케이스 만들어봐도 제가 만든 건 다 예상값이 나오는데. 혹시 어디서 잘못되었는지 도와주시면 감사하겠습니다ㅠㅜ import sys sys.setrecursionlimit(1000000000) input = sys.stdin.readline n, m = map(int, input().rstrip().split()) S = input().rstrip() T = {i+1: set() for i in range(n)} for _ in range(n-1):     u, v, c = list(input().rstrip().split())     u, v = int...

실행시간 줄일만한 부분 좀 찾아주실 수 있으신가요?

테케 4번, 19번에서 0.1초 오버되어서 시간 초과 뜨는데 어디서 줄일 수 있을지 감이 안잡히네요 ㅠㅠ import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.HashMap; import java.util.StringTokenizer; public class Main { public static BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); public static StringTokenizer st; public static ArrayList<String> results; public static int[][] dp; public static char map[][]; static int n; public...

일부 테스트 케이스에서만 오답이 뜨는데 이유를 모르겠습니다ㅠ

#include<iostream> #include<vector> #include<string> using namespace std; int N, M; string S; bool *visited; vector<pair<int, char>> *tree; int dp[5005][5005] = {0,}; int lcs = 0; void dfs(int num, int depth){     bool is_leaf = true;     visited[num] = true;     for(pair<int, char> p : tree[num]){         if(!visited[p.first]){             visited[p.first] = true;             is_leaf = false;             for(int i = 1; i <= S.length(); i++){                 if(S...

max 연산자 시간소요 관련

mport sys input = sys.stdin.readline sys.setrecursionlimit(5000) n, m = map(int, input().split()) s = input() graph = [ [] for _ in range(5003)] visited = [False] * 5003 d = [[0]*5003 for _ in range(5003)] ans = 0 def dfs(u, level, road) : global ans visited[u] = True for i in range(m+1) : if level == 0 or i ==0 : d[level][i] = 0 elif road[level-1] == s[i-1] : d[level][i] = d[level-1][i-1] + 1 else : ...

시간 초과 관련 문의

import sys sys.setrecursionlimit(10000) n, m = map(int, sys.stdin.readline().split()) s = sys.stdin.readline() h = [[""]*(n+1) for _ in range(n+1)] graph = [ [] for _ in range(n+1)] for i in range(n-1) : u, v, c = map(str, sys.stdin.readline().split()) u, v = int(u), int(v) h[u][v] = str(c) h[v][u] = str(c) graph[u].append(v) graph[v].append(u) #print(graph) visited = [0] * (n+1) visited[1] = 1 ans = -1 def LCS(b) : global ans a_len = l...

이 문제 파이썬으로 푸시는 분들 재귀 dfs 사용하실거면

import sys sys.setrecursionlimit(5000) 꼭 해주세요

테스트 케이스 확인 부탁드려도 될까요?

파이썬으로 TC 4번이 아무리 해도 통과가 안되는 것 같아요... 자바로는 특별히 branching 하지 않아도 모든 테스트 케이스가 통과하는데 파이썬이 통과가 안되요 ㅜㅜ 4번 테케만 실패하는 파이썬 코드 from collections import deque import sys N, M = map(int, sys.stdin.readline().split()) S = sys.stdin.readline() answer = 0 graphs = [[] for _ in range(N+1)] for _ in range(N-1): a = sys.stdin.readline().split() start, end, spell = int(a[0]), int(a[1]), a[2] graphs[start].append((end, spell)) graphs[end].append((start, spell)) ### 리프 노드 찾기 ###...

어디서 잘못되엇느지 모르겟습니다...

dfs로 모든 경로를 찾고 각 경로를 LCS로 행복지수의 최대 값을 구하도록 구현하였습니다. 어디가 잘못되었을까요? import java.io.*; import java.util.*; public class Main { public static String[][] tree; public static boolean[][] visited; public static int N; public static ArrayList<String> ways = new ArrayList<>(); public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new StringTokenizer(br.readLine()); //입력 N = Integer.parseInt(st.nextToken...