首頁 web前端 html教學 CF 题目集锦 PART 5 #266 div 2 E_html/css_WEB-ITnose

CF 题目集锦 PART 5 #266 div 2 E_html/css_WEB-ITnose

Jun 24, 2016 am 11:57 AM
cf div

【原题】

E. Information Graph

time limit per test

1 second

memory limit per test

512 megabytes

input

standard input

output

standard output

There are n employees working in company "X" (let's number them from 1 to n for convenience). Initially the employees didn't have any relationships among each other. On each of m next days one of the following events took place:

  • either employee y became the boss of employee x (at that, employee x didn't have a boss before);
  • or employee x gets a packet of documents and signs them; then he gives the packet to his boss. The boss signs the documents and gives them to his boss and so on (the last person to sign the documents sends them to the archive);
  • or comes a request of type "determine whether employee x signs certain documents".
  • Your task is to write a program that will, given the events, answer the queries of the described type. At that, it is guaranteed that throughout the whole working time the company didn't have cyclic dependencies.

    Input

    The first line contains two integers n and m (1?≤?n,?m?≤?105) ? the number of employees and the number of events.

    Each of the next m lines contains the description of one event (the events are given in the chronological order). The first number of the line determines the type of event t (1?≤?t?≤?3).

  • If t?=?1, then next follow two integers x and y (1?≤?x,?y?≤?n) ? numbers of the company employees. It is guaranteed that employee x doesn't have the boss currently.
  • If t?=?2, then next follow integer x (1?≤?x?≤?n) ? the number of the employee who got a document packet.
  • If t?=?3, then next follow two integers x and i (1?≤?x?≤?n; 1?≤?i?≤?[number of packets that have already been given]) ? the employee and the number of the document packet for which you need to find out information. The document packets are numbered started from 1 in the chronological order.
  • It is guaranteed that the input has at least one query of the third type.

    Output

    For each query of the third type print "YES" if the employee signed the document package and "NO" otherwise. Print all the words without the quotes.

    Sample test(s)

    input

    4 91 4 32 43 3 11 2 32 23 1 21 3 12 23 1 3
    登入後複製

    output

    YESNOYES
    登入後複製

    【题意】意思看了半天~就是有N个人,M个操作。每次操作有3种。

    ①把x的父亲置为y。

    ②从x开始发新的一份文件(是从1开始标号的)。从x开始,一直传递到最远的祖先。

    ③询问x号文件有没有落到y的手里。

    【分析】即要简单地判断y是否是x的祖先。一开始有思维定势,觉得要求一遍LCA。但是后来想了想,可以直接用DFS序搞出同一棵树的深度,再用并查集维护是否在同一棵树上。代码很简单。

    【代码】

    #include<cstdio>#include<vector>#define N 200005#define pb push_backusing namespace std;vector<int>son[N],ask[N];struct arr{int x,y,id,opt;}a[N];int f[N],L[N],R[N],fa[N],ans[N];int i,n,m,now,num,id,tot,P,j;inline int get(int u){return f[u]==u?f[u]:f[u]=get(f[u]);}void dfs(int k){  L[k]=++tot;  for (int i=0;i<son dfs r main scanf for if son ask f id="ask[now][j];num=a[id].x;">=R[a[i].x]) ans[id]=1;    }  }}</son></int></vector></cstdio>
    登入後複製

    本網站聲明
    本文內容由網友自願投稿,版權歸原作者所有。本站不承擔相應的法律責任。如發現涉嫌抄襲或侵權的內容,請聯絡admin@php.cn

    熱AI工具

    Undresser.AI Undress

    Undresser.AI Undress

    人工智慧驅動的應用程序,用於創建逼真的裸體照片

    AI Clothes Remover

    AI Clothes Remover

    用於從照片中去除衣服的線上人工智慧工具。

    Undress AI Tool

    Undress AI Tool

    免費脫衣圖片

    Clothoff.io

    Clothoff.io

    AI脫衣器

    Video Face Swap

    Video Face Swap

    使用我們完全免費的人工智慧換臉工具,輕鬆在任何影片中換臉!

    熱門文章

    <🎜>:泡泡膠模擬器無窮大 - 如何獲取和使用皇家鑰匙
    3 週前 By 尊渡假赌尊渡假赌尊渡假赌
    北端:融合系統,解釋
    3 週前 By 尊渡假赌尊渡假赌尊渡假赌
    Mandragora:巫婆樹的耳語 - 如何解鎖抓鉤
    3 週前 By 尊渡假赌尊渡假赌尊渡假赌

    熱工具

    記事本++7.3.1

    記事本++7.3.1

    好用且免費的程式碼編輯器

    SublimeText3漢化版

    SublimeText3漢化版

    中文版,非常好用

    禪工作室 13.0.1

    禪工作室 13.0.1

    強大的PHP整合開發環境

    Dreamweaver CS6

    Dreamweaver CS6

    視覺化網頁開發工具

    SublimeText3 Mac版

    SublimeText3 Mac版

    神級程式碼編輯軟體(SublimeText3)

    熱門話題

    Java教學
    1666
    14
    CakePHP 教程
    1425
    52
    Laravel 教程
    1325
    25
    PHP教程
    1273
    29
    C# 教程
    1252
    24
    cf羅技一鍵宏怎麼設定? cf羅技滑鼠宏​​設置 cf羅技一鍵宏怎麼設定? cf羅技滑鼠宏​​設置 Mar 14, 2024 pm 10:50 PM

      滑鼠巨集為滑鼠鍵賦予一系列複雜的操作,可以簡單地理解為滑鼠的快捷鍵設置,點擊設置滑鼠巨集的按鍵後,就能完成一些平時無法做到的操作。那麼玩cf要如何設定滑鼠巨集呢?下面就來看看cf羅技滑鼠巨集設定教學吧。  1、首先是在電腦安裝Logitech遊戲軟體,然後點選如圖中箭頭所示,開啟自訂按鈕的設定介面。接著,您需要選擇一個鍵,例如左鍵,點擊小箭頭,然後在彈出的選單中選擇“編輯命令”,這樣就可以打開左鍵巨集的設定介面。  3、接著就是點擊按鈕,如圖中紅箭頭所示,點選文字方塊隨便輸入一個按鍵,注意的是例如A

    css怎麼實作div缺一個角 css怎麼實作div缺一個角 Jan 30, 2023 am 09:23 AM

    css實作div缺少一個角的方法:1、建立一個HTML範例文件,並定義一個div;2、給div設定寬高背景色;3、給需要刪除一角的div增加一個偽類,將偽類設定成跟背景色一樣的顏色,然後旋轉45度,再定位到需要去除的那個角落即可。

    iframe和div有什麼不同 iframe和div有什麼不同 Aug 28, 2023 am 11:46 AM

    iframe和div的不同是iframe主要用於引入外部內容,可以載入其他網站的內容或將一個網頁分割成多個區域,每個區域有自己的獨立的瀏覽上下文,而div主要用於分割和組織內容的區塊,用於佈局和样式控制。

    基於 ChatGPT API 的劃詞翻譯瀏覽器腳本實現 基於 ChatGPT API 的劃詞翻譯瀏覽器腳本實現 May 01, 2023 pm 03:28 PM

    前言最近GitHub上有個基於ChatGPTAPI的瀏覽器腳本,openai-translator,短時間內star衝到了12k,功能上除了支援翻譯外,還支援潤飾和總結功能,除了瀏覽器插件外,還使用了tauri打包了一個桌面客戶端,那拋開tauri是使用rust部分,那瀏覽器部分實作還是比較簡單的,今天我們就來手動實作一下。 openAI提供的介面例如我們可以複製以下程式碼,在瀏覽器控制台中發起請求,就可以完成翻譯//範例constOPENAI_API_KEY="s

    div盒模型是什麼 div盒模型是什麼 Oct 09, 2023 pm 05:15 PM

    div盒模型是用於網頁佈局的模型,它將網頁中的元素視為一個個矩形的盒子,這個模型包含了四個部分:內容區域、內邊距、邊框和外邊距。 div盒模型的好處是可以輕鬆控制網頁佈局和元素之間的間距,透過調整內容區域、內邊距、邊框和外邊距的大小,可以實現各種不同的佈局效果,盒模型也提供了一些屬性和方法,可以透過CSS和JavaScript來動態地改變盒子的樣式和行為。

    div與span的差別有哪些 div與span的差別有哪些 Nov 02, 2023 pm 02:29 PM

    差異有:1、div是一個區塊級元素,span是一個行內元素;2、div會自動佔據一行,span則不會自動換行;3、div用於包裹比較大的結構和佈局,span用於包裹文字或其他行內元素;4、div可以包含其他區塊級元素和行內元素,span可以包含其他行內元素。

    WIN10系統cf怎麼調煙霧頭 WIN10系統cf怎麼調煙霧頭 Feb 26, 2024 pm 04:17 PM

    調整步驟:1、在Win10系統桌面,右鍵點選開始按鈕,選擇「設定」;2、點選「系統」圖示;3、點選左側側邊欄的「顯示」選單項目;4、在右側點選「顯示適配器屬性」快捷連結;5、點選「列出所有模式」按鈕;6、從所有模式中選擇「1024*768真彩色60赫茲」一項;7、點擊上面的「監視器」標籤,將其設定為60赫茲;8、點選“確定”,然後重新啟動電腦即可。

    如何將兩個div並排顯示 如何將兩個div並排顯示 Nov 01, 2023 am 11:36 AM

    方法有:1、將兩個div元素設定為「float:left;」屬性;2、使用CSS的flex佈局可以輕鬆實現元素的並排顯示;3、使用CSS的grid佈局也可以實現元素的並排顯示。

    See all articles