Cerinta completa

In the middle of a nightmare, Maxine suddenly finds herself in a mysterious room with the following items:

  1. A piece of paper with the word score and the integer written on it.
  2. A map of the castle where the room is located.
    • There are rooms uniquely labeled from to .
    • There are bidirectional corridors connecting pairs of rooms. The value of score changes every time she travels up or down a corridor, and this value differs depending on her direction of travel along the corridor. Each corridor can be traveled any number of times in either direction.
    • Every room is reachable from every other room.
    • Maxine is located in the room labeled .
    • The exit is located in the room labeled . Once this room is reached, score is reduced modulo and Maxine can (but is not required to) exit that level!

Assume some corridor (where ) is associated with an integer, , and connects rooms and . Then:

  • Traveling corridor from room to room increases score by .
  • Traveling corridor from room to room decreases score by .

There are levels to Maxine’s nightmare castle, and each one has a different set of values for , , and . Given the above information, help Maxine by finding and printing her maximum possible score for each level. Only you can help her wake up from this nightmare!

Note: Recall that the result of a modulo operation is always non-negative. For example, .

Input Format

The first line contains a single integer, , denoting the number of rooms.
Each of the subsequent lines describes a corridor in the form of three space-separated integers denoting the respective values for , , and .
The next line contains a single integer, , denoting the number of queries.
Each of the subsequent lines describes a level in the form of three space-separated integers denoting its respective , , and values.

Constraints

  • ,

For each level:

  • The room layout is the same

Subtask

  • for of max score.

Output Format

For each of the levels, print the maximum possible score for that level on a new line.

Sample Input

3
1 3 5
2 3 8
2 1 31
1
1 2 13

Sample Output

12

Explanation

The Sample Input represents the following setup:

We want to travel from room to room while maximizing the value of score. There are at least two ways to achieve the maximum score value of :

  1. Travel through corridors times:

    .

  2. Travel through corridors times:
    , because is the smallest non-negative integer such that divides .

Limbajul de programare folosit: cpp

Cod:

#include <cstdio>
#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <string>
#include <set>
#include <map>
#include <ctime>
#include <cstring>
#include <cassert>
#include <bitset>
#include <sstream>
#include <queue>

#define pb push_back
#define mp make_pair
#define fs first
#define sc second
#define sz(a) ((int) (a).size())
#define eprintf(...) fprintf(stderr, __VA_ARGS__)

using namespace std;

typedef long long int64;
typedef long double ldb;

const long double eps = 1e-9;
const int inf = (1 << 30) - 1;
const long long inf64 = ((long long)1 << 62) - 1;
const long double pi = acos(-1);

template <class T> T sqr (T x) {return x * x;}
template <class T> T abs (T x) {return x < 0 ? -x : x;}

const int MAXN = 120 * 1000;

vector <pair <int, int> > adj[MAXN];
long long a[MAXN];
bool used[MAXN];
long long cycle = 0;

void dfs(int v, long long num) {
    a[v] = num;
    used[v] = true;
    for (int i = 0; i < sz(adj[v]); ++i) {
        int u = adj[v][i].fs;
        if (!used[u]) {
            dfs(u, num + adj[v][i].sc);
        } else if (a[v] + adj[v][i].sc - a[u] != 0) {
            cycle = a[v] + adj[v][i].sc - a[u];
        }
    }
}

int gcd(int a, int b) {
    return (a == 0 ? b : gcd(b % a, a));
}

int main () {

    int n;
    scanf("%d", &n);
    for (int i = 0; i < n; ++i) {
        int v1, v2, c;
        scanf("%d%d%d", &v1, &v2, &c);
        v1--, v2--;
        adj[v1].pb(mp(v2, c));
        adj[v2].pb(mp(v1, -c));
    }

    dfs(0, 0);
    
    int q;
    scanf("%d", &q);
    for (int i = 0; i < q; ++i) {
        int s, e, m;
        scanf("%d%d%d", &s, &e, &m);
        s--, e--;
        
        int val = ((a[e] - a[s]) % m + m) % m;
        int cycle_val = (cycle % m  + m) % m;
        
        int d = gcd(cycle_val, m);

        int res = (val % d) + m - d;
        printf("%d\n", res);
    }

    return 0;
}

Scor obtinut: 1.0

Submission ID: 464646133

Link challenge: https://www.hackerrank.com/challenges/longest-mod-path/problem

Longest Mod Path