codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

29.md (1025B)


      1 Source: https://codeforces.com/blog/entry/686
      2 
      3 Problem A:  
      4 Check whether exist a pair i and j,they satisfy xi+di = xj && xj+dj = xi;  
      5   
      6 Problem B:  
      7 Pay attention to Just Right or Red. use Div and Mod can solve it easily;  
      8   
      9 Problem C:  
     10 As we know, there are only two path -- forward and reverse, so we can do DFS from the one-degree nodes (only two nodes).  
     11 As their index may be very larger, so I used map<int,int> to do hash.  
     12   
     13 void dfs(int i)  
     14 {  
     15      int sz = mat[i].size()-1, j;  
     16      UF(j,0,sz)  
     17      if (!vis[mat[i][j]])  
     18      {  
     19         vis[mat[i][j]] = 1;  
     20         printf(" %d",val[mat[i][j]]);  
     21         dfs(mat[i][j]);  
     22      }  
     23 }  
     24   
     25 Problem D:   
     26 Floyd.  
     27 First, Floyd pretreat the path from I to J, and save the path.   
     28 Then get the answer.  
     29 The order is a1,a2...ak, K is the number of the leaves, we can assume a0 = ak+1 = 1, the root.  
     30 then, answer push_back the path[ai][ai+1].  
     31   
     32 if the ans.size() > 2*N-1 , cout -1;  
     33 else cout the answer.