Dream and the Multiverse Solution Codechef

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

February Long Challenge 2021

Leave a Comment