Submission #208061

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
208061	2020-03-10 00:07:43	ly20	Railway (BOI17_railway)	C++17	100 / 100	266 ms	37128 KiB

railway

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 112345, MAXK = 20;
int t;
vector < int > grafo[MAXN];
int marc[MAXN], dp[MAXN][MAXK], prof[MAXN];
int id[MAXN];
void dfs(int v, int p) {
  dp[v][0] = p;
  t++;
  id[v] = t;
  for(int i = 0; i < grafo[v].size(); i++) {
    int viz = grafo[v][i];
    if(viz == p) continue;
    prof[viz] = prof[v] + 1;
    dfs(viz, v);
  }
}
int lca(int a, int b) {
  if(prof[a] > prof[b]) swap(a, b);
  int d = prof[b] - prof[a];
  for(int i = 0; i < MAXK; i++) {
    if((1 << i) & d) b = dp[b][i];
  }
  if(a == b) return a;
  for(int i = MAXK - 1; i >= 0; i--) {
    if(dp[a][i] != dp[b][i]) {
      a = dp[a][i]; b = dp[b][i];
    }
  }
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

Compilation message (stderr)

railway.cpp: In function 'void dfs(int, int)':
railway.cpp:12:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < grafo[v].size(); i++) {
                 ~~^~~~~~~~~~~~~~~~~
railway.cpp: In function 'void dfs2(int, int)':
railway.cpp:34:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < grafo[v].size(); i++) {
                 ~~^~~~~~~~~~~~~~~~~
railway.cpp: In function 'int main()':
railway.cpp:83:28: warning: format '%d' expects argument of type 'int', but argument 2 has type 'std::vector<int>::size_type {aka long unsigned int}' [-Wformat=]
  printf("%d\n", resp.size());
                 ~~~~~~~~~~~^
railway.cpp:84:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < resp.size(); i++) {
                 ~~^~~~~~~~~~~~~
railway.cpp:47:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d %d", &n, &m, &k);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
railway.cpp:50:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d", &a, &b); a--; b--;
   ~~~~~^~~~~~~~~~~~~~~~~
railway.cpp:62:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &s);
   ~~~~~^~~~~~~~~~
railway.cpp:66:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d", &a); a--;
    ~~~~~^~~~~~~~~~

• Subtask 1: 8 / 8
• Subtask 2: 15 / 15
• Subtask 3: 7 / 7
• Subtask 4: 29 / 29
• Subtask 5: 16 / 16
• Subtask 6: 25 / 25