Longest Mod Path
Problem Statement :
n the middle of a nightmare, Maxine suddenly finds herself in a mysterious room with the following items: A piece of paper with the word score and the integer written on it. 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
Solution :
Solution in C :
In C++ :
#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 () {
// ios_base::sync_with_stdio(0);
// freopen("input.txt", "rt", stdin);
// freopen("output.txt", "wt", stdout);
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;
// cerr << val << " " << cycle_val << " " << m << endl;
int d = gcd(cycle_val, m);
// cerr << d << endl;
int res = (val % d) + m - d;
printf("%d\n", res);
}
return 0;
}
In C :
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define HASH_SIZE 123455
#define INF 1000000007
typedef struct _node{
int x;
int y;
int w;
struct _node *next;
} node;
typedef struct _lnode{
int x;
int w;
struct _lnode *next;
} lnode;
void insert_edge(int x,int y,int w);
void dfs0(int x,int y);
void dfs1(int x);
void get_loop(int x,int y);
long long CC(long long n, long long d);
void insert(int x,int y,int w);
int search(int x,int y);
lnode *table[100000]={0};
node *hash[HASH_SIZE]={0};
int loop[100000]={0},trace[100000]={0},point[100000];
int first_point,breakp=0,cycle_found=0;
long long cycle=0,dis[100000]={0},cycle_save;
int main(){
int N,a,b,x,S,E,M,Q,MOD,DIS,GCD,ans,i;
scanf("%d",&N);
for(i=0;i<N;i++){
scanf("%d%d%d",&a,&b,&x);
insert_edge(a-1,b-1,x);
if(a>b)
Q=search(b-1,a-1);
else
Q=search(a-1,b-1);
if(Q==INF)
if(a>b)
insert(b-1,a-1,-x);
else
insert(a-1,b-1,x);
else{
if(a>b)
cycle=x+Q;
else
cycle=x-Q;
cycle_found=1;
cycle_save=cycle;
}
}
dfs0(0,-1);
if(!loop[0])
point[0]=first_point;
memset(trace,0,sizeof(trace));
dfs1(0);
if(cycle_found)
cycle=cycle_save;
scanf("%d",&Q);
while(Q--){
scanf("%d%d%d",&S,&E,&M);
MOD=(cycle%M+M)%M;
DIS=((dis[E-1]-dis[S-1])%M+M)%M;
if(!MOD)
ans=DIS;
else{
GCD=CC(MOD,M);
ans=(M-1-DIS)/GCD*GCD+DIS;
}
printf("%d\n",ans);
}
return 0;
}
void insert_edge(int x,int y,int w){
lnode *t=malloc(sizeof(lnode));
t->x=y;
t->w=w;
t->next=table[x];
table[x]=t;
t=malloc(sizeof(lnode));
t->x=x;
t->w=-w;
t->next=table[y];
table[y]=t;
return;
}
void dfs0(int x,int y){
lnode *p;
trace[x]=1;
for(p=table[x];p;p=p->next)
if(!trace[p->x]){
dis[p->x]=dis[x]+p->w;
dfs0(p->x,x);
}
else if(p->x!=y && !loop[p->x]){
first_point=p->x;
get_loop(p->x,-1);
cycle+=p->w;
}
return;
}
void dfs1(int x){
lnode *p;
trace[x]=1;
if(loop[x])
point[x]=x;
for(p=table[x];p;p=p->next)
if(!trace[p->x]){
if(!loop[p->x])
point[p->x]=point[x];
dfs1(p->x);
}
return;
}
void get_loop(int x,int y){
lnode *p;
loop[x]=1;
for(p=table[x];p && !breakp;p=p->next)
if(trace[p->x] && !loop[p->x]){
cycle+=p->w;
get_loop(p->x,x);
if(!breakp)
cycle-=p->w;
}
else if(p->x==first_point && p->x!=y){
breakp=1;
break;
}
return;
}
long long CC(long long n, long long d){
while( 1 )
{
n = n % d;
if( n == 0 )
return d;
d = d % n;
if( d == 0 )
return n;
}
}
void insert(int x,int y,int w){
int bucket=(x*100000LL+y)%HASH_SIZE;
node *t;
t=(node*)malloc(sizeof(node));
t->x=x;
t->y=y;
t->w=w;
t->next=hash[bucket];
hash[bucket]=t;
return;
}
int search(int x,int y){
int bucket=(x*100000LL+y)%HASH_SIZE;
node *t=hash[bucket];
while(t){
if(t->x==x && t->y==y)
return t->w;
t=t->next;
}
return INF;
}
In Python3 :
from fractions import gcd
n=int(input())
adjlst = [[] for i in range(n)]
for j in range(0,n):
arr=list(map(int,input().split()))
a=arr[0]-1
b=arr[1]-1
c=arr[2]
adjlst[a].append((b,c))
adjlst[b].append((a,-c))
dist = [None]*n
parents = [set() for i in range(n)]
dist[0] = 0
stack = [0]
while stack:
i = stack.pop()
for j, c in adjlst[i]:
if j in parents[i]: continue
dist1 = dist[i] + c
parents[j].add(i)
if dist[j] is None:
dist[j] = dist1
stack.append(j)
else:
cycle = abs(dist[j] - dist1)
q=int(input())
for j in range(0,q):
arr1=list(map(int,input().split()))
s=arr1[0]
e=arr1[1]
m=arr1[2]
a = gcd(cycle, m)
print (m - a + (dist[e-1] - dist[s-1]) % a)
View More Similar Problems
Components in a graph
There are 2 * N nodes in an undirected graph, and a number of edges connecting some nodes. In each edge, the first value will be between 1 and N, inclusive. The second node will be between N + 1 and , 2 * N inclusive. Given a list of edges, determine the size of the smallest and largest connected components that have or more nodes. A node can have any number of connections. The highest node valu
View Solution →Kundu and Tree
Kundu is true tree lover. Tree is a connected graph having N vertices and N-1 edges. Today when he got a tree, he colored each edge with one of either red(r) or black(b) color. He is interested in knowing how many triplets(a,b,c) of vertices are there , such that, there is atleast one edge having red color on all the three paths i.e. from vertex a to b, vertex b to c and vertex c to a . Note that
View Solution →Super Maximum Cost Queries
Victoria has a tree, T , consisting of N nodes numbered from 1 to N. Each edge from node Ui to Vi in tree T has an integer weight, Wi. Let's define the cost, C, of a path from some node X to some other node Y as the maximum weight ( W ) for any edge in the unique path from node X to Y node . Victoria wants your help processing Q queries on tree T, where each query contains 2 integers, L and
View Solution →Contacts
We're going to make our own Contacts application! The application must perform two types of operations: 1 . add name, where name is a string denoting a contact name. This must store name as a new contact in the application. find partial, where partial is a string denoting a partial name to search the application for. It must count the number of contacts starting partial with and print the co
View Solution →No Prefix Set
There is a given list of strings where each string contains only lowercase letters from a - j, inclusive. The set of strings is said to be a GOOD SET if no string is a prefix of another string. In this case, print GOOD SET. Otherwise, print BAD SET on the first line followed by the string being checked. Note If two strings are identical, they are prefixes of each other. Function Descriptio
View Solution →Cube Summation
You are given a 3-D Matrix in which each block contains 0 initially. The first block is defined by the coordinate (1,1,1) and the last block is defined by the coordinate (N,N,N). There are two types of queries. UPDATE x y z W updates the value of block (x,y,z) to W. QUERY x1 y1 z1 x2 y2 z2 calculates the sum of the value of blocks whose x coordinate is between x1 and x2 (inclusive), y coor
View Solution →