Page Contents
Dream and the Multiverse Solution February Challenge 2021
Dream abstracts the fabric of spacetime as a directed rooted tree (arborescence) with NN nodes (numbered 11 through NN). Node 11 is the root and for each ii (1≤i≤N−11≤i≤N−1), the parent of node i+1i+1 is fifi. All edges of this tree are directed away from the root.
Then, Dream employs a magical superpower and adds MM directed edges to this tree in such a way that the resulting directed graph remains acyclic (a DAG).
Let’s call a node of this DAG an event and further call a simple path on this DAG an era. Dream considers a pair of events (i,j)(i,j) to be plausible if there is an era whose first event is ii and last event is jj. Note that i<ji<j does not have to hold for a plausible pair.
Dream now wants you to answer QQ queries. In each query, he gives you two positive integers ll and rr, where l≤rl≤r, and he wishes to know the number of plausible pairs of events (i,j)(i,j) such that l≤i<j≤rl≤i<j≤r.
Also See: February Long Challenge 2021 Solutions
Input
- The first line of the input contains two space-separated integers NN and MM.
- The second line contains N−1N−1 space-separated integers f1,f2,…,fN−1f1,f2,…,fN−1.
- MM lines follow. Each of these lines contains two space-separated integers uu and vv describing an additional edge from node uu to node vv.
- The following line contains a single integer QQ.
- QQ lines follow. Each of these lines contains two space-separated integers ll and rr describing a query.
Output
For each query, print a single line containing one integer ― the number of plausible pairs (i,j)(i,j) such that l≤i<j≤rl≤i<j≤r.
Constraints
- 2≤N≤3⋅1052≤N≤3⋅105
- 1≤Q≤3⋅1051≤Q≤3⋅105
- 0≤M≤200≤M≤20
- 1≤fi≤N1≤fi≤N for each valid ii
- 1≤u,v≤N1≤u,v≤N
- the graph described on the input is acyclic
- 1≤l≤r≤N1≤l≤r≤N
Subtasks
Subtask #1 (10 points): the graph is a line ― that is, M=0M=0 and there is a permutation p1,p2,…,pNp1,p2,…,pN such that p1=1p1=1 and nodes p1,p2,…,pNp1,p2,…,pN form a directed path in the tree
Subtask #2 (20 points): M=0M=0
Subtask #3 (30 points): N,Q≤2⋅105N,Q≤2⋅105
Subtask #4 (40 points): original constraints
Example Input
8 2 1 2 5 1 4 3 3 2 4 4 7 3 4 6 5 7 1 8
Example Output
2 2 18
Follow us on telegram for quick update an abundance of free knowledge: Click Here
Solution
Program C++:
#include <bits/stdc++.h> using namespace std; const int MOD = 998244353; const int MAX = 1e6 + 5; typedef long long ll; mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); int main() { int n,m,r; cin>>n>>m>>r; map<pair<int,int>, vector<int>> M; for(int i=1;i<=n;i++) { int x,y; cin>>x>>y; } for(int i=1;i<=m;i++) { vector<int> PP(3); cin>>PP[0]>>PP[1]>>PP[2]; sort(PP.begin(), PP.end()); M[{PP[0],PP[1]}].push_back(PP[2]); M[{PP[0],PP[2]}].push_back(PP[1]); M[{PP[1],PP[2]}].push_back(PP[0]); } for(int i=1;i<=r;i++) { int b; cin>>b; } vector<pair<int,int>> Flips; set<pair<int,int>> Poss_Lines; for(auto m:M) { if(m.second.size()==2) { Poss_Lines.insert(m.first); } } // int F = rng()%30; cout<<"0"<<endl; // for(int i=0;i<F;i++) // { // int which = rng()%Poss_Lines.size(); // int curr=0; // for(auto f:Poss_Lines) // { // if(curr==which) // { // cout<<f.first<<" "<<f.second<<endl; // Flips.push_back(f); // break; // } // curr++; // } // Poss_Lines.erase(Flips.back()); // int x = M[Flips.back()][0]; // int y = M[Flips.back()][1]; // if(x>y) swap(x,y); // M[{x,y}] = {Flips.back().first,Flips.back().second}; // Poss_Lines.insert({x,y}); // } for(int i=0;i<m-r;i++) { int which = rng()%Poss_Lines.size(); int curr=0; for(auto f:Poss_Lines) { if(curr==which) { cout<<f.first<<" "<<f.second<<endl; Poss_Lines.erase(f); break; } curr++; } } }
Program Java:
/* package codechef; // don't place package name! */ import java.math.BigInteger; import java.util.*; import java.lang.*; import java.io.*; import java.io.DataInputStream; import java.io.FileInputStream; import java.io.IOException; import java.io.InputStreamReader; import java.util.Scanner; import java.util.StringTokenizer; /* Name of the class has to be "Main" only if the class is public. */ class Codechef { static class Reader { final private int BUFFER_SIZE = 1 << 16; private DataInputStream din; private byte[] buffer; private int bufferPointer, bytesRead; public Reader() { din = new DataInputStream(System.in); buffer = new byte[BUFFER_SIZE]; bufferPointer = bytesRead = 0; } public Reader(String file_name) throws IOException { din = new DataInputStream(new FileInputStream(file_name)); buffer = new byte[BUFFER_SIZE]; bufferPointer = bytesRead = 0; } public String readLine() throws IOException { byte[] buf = new byte[64]; // line length int cnt = 0, c; while ((c = read()) != -1) { if (c == '\n') break; buf[cnt++] = (byte) c; } return new String(buf, 0, cnt); } public int nextInt() throws IOException { int ret = 0; byte c = read(); while (c <= ' ') c = read(); boolean neg = (c == '-'); if (neg) c = read(); do { ret = ret * 10 + c - '0'; } while ((c = read()) >= '0' && c <= '9'); if (neg) return -ret; return ret; } public long nextLong() throws IOException { long ret = 0; byte c = read(); while (c <= ' ') c = read(); boolean neg = (c == '-'); if (neg) c = read(); do { ret = ret * 10 + c - '0'; } while ((c = read()) >= '0' && c <= '9'); if (neg) return -ret; return ret; } public double nextDouble() throws IOException { double ret = 0, div = 1; byte c = read(); while (c <= ' ') c = read(); boolean neg = (c == '-'); if (neg) c = read(); do { ret = ret * 10 + c - '0'; } while ((c = read()) >= '0' && c <= '9'); if (c == '.') { while ((c = read()) >= '0' && c <= '9') { ret += (c - '0') / (div *= 10); } } if (neg) return -ret; return ret; } private void fillBuffer() throws IOException { bytesRead = din.read(buffer, bufferPointer = 0, BUFFER_SIZE); if (bytesRead == -1) buffer[0] = -1; } private byte read() throws IOException { if (bufferPointer == bytesRead) fillBuffer(); return buffer[bufferPointer++]; } public void close() throws IOException { if (din == null) return; din.close(); } } /*---------------------------------------------------------------------------------------------- public static long mod=1000000007; public static long power(long a, long b) { if(b == 0) return 1; long answer = power(a, b/2)%mod; answer = (answer*answer)%mod; if(b%2!=0) answer = (answer*a)%mod; return answer; } public static long min(long a, long b) { return a<b?a:b; } public static long divide(long a,long b) { return (a%mod*(power(b, mod-2)%mod))%mod; } public static long nCr(long n,long r) { long answer = 1; long k = min(r, n-r); for(long i=0;i<k;i++) { answer = (answer%mod*(n-i)%mod)%mod; answer = divide(answer, i+1); } return answer%mod; } public static boolean plaindrome(String str){ StringBuilder sb=new StringBuilder(); sb.append(str); return (str.equals((sb.reverse()).toString())); } ----------------------------------------------------------------------------------------------*/ static class Graph { private int V; // No. of vertices private LinkedList<Integer> adj[]; //Adjacency List //Constructor Graph(int v) { V = v; adj = new LinkedList[v]; for (int i=0; i<v; ++i) adj[i] = new LinkedList(); } //Function to add an edge into the graph void addEdge(int v,int w) { adj[v].add(w); } //prints BFS traversal from a given source s Boolean isReachable(int s, int d) { LinkedList<Integer>temp; // Mark all the vertices as not visited(By default set // as false) boolean visited[] = new boolean[V]; // Create a queue for BFS LinkedList<Integer> queue = new LinkedList<Integer>(); // Mark the current node as visited and enqueue it visited[s]=true; queue.add(s); // 'i' will be used to get all adjacent vertices of a vertex Iterator<Integer> i; while (queue.size()!=0) { // Dequeue a vertex from queue and print it s = queue.poll(); int n; i = adj[s].listIterator(); // Get all adjacent vertices of the dequeued vertex s // If a adjacent has not been visited, then mark it // visited and enqueue it while (i.hasNext()) { n = i.next(); // If this adjacent node is the destination node, // then return true if (n==d) return true; // Else, continue to do BFS if (!visited[n]) { visited[n] = true; queue.add(n); } } } // If BFS is complete without visited d return false; } } public static void main (String[] args) throws java.lang.Exception { Reader s=new Reader(); StringBuilder sb=new StringBuilder(); int n=s.nextInt(); int m=s.nextInt(); Graph g = new Graph(n); for(int i=1;i<n;i++){ int k=s.nextInt(); g.addEdge(i,k); } for(int i=0;i<m;i++){ int a=s.nextInt(); int b=s.nextInt(); g.addEdge(a,b); } boolean arr[][]=new boolean[n][n]; for(int i=0;i<n;i++){ for(int j=0;j<n;j++){ if(i==j)continue; arr[i][j]=g.isReachable(i, j); } } int q=s.nextInt(); while(q-->0){ int a=s.nextInt()-1; int b=s.nextInt()-1; int ans=0; for(int i=a;i<=b;i++){ for(int j=i+1;j<=b;j++){ if(arr[i][j])ans++; } } System.out.println(ans); } } }
Codechef Long Challenges
September Long Challenge 2021 Solution
- Airline Restrictions
- Travel Pass
- Shuffling Parities
- XOR Equal
- 2-D Point Meeting
- Minimize Digit Sum
- Minimum Digit Sum 2
- Treasure Hunt
- Covaxin vs Covishield
February Long Challenge 2021
- Frog Sort Solution Codechef
- Chef and Meetings Solution Codechef
- Maximise Function Solution Codechef
- Highest Divisor Solution Codechef
- Cut the Cake Challenge Solution Codechef
- Dream and the Multiverse Solution Codechef
- Cell Shell Solution Codechef
- Multiple Games Solution Codechef
- Another Tree with Number Theory Solution Codechef
- XOR Sums Solution Codechef
- Prime Game Solution CodeChef
- Team Name Solution Codechef
- Bash Matrix Solution CodeChef