Submission #88890

#	Time	Username	Problem	Language	Result	Execution time	Memory
88890		zviki	Triumphal arch (POI13_luk)	C++14	100 / 100	1460 ms	30596 KiB

luk

    #include <bits/stdc++.h>
     
    using namespace std;
     
    int n;
    vector < int > G[300020];
    int answer[300020];
     
    void go(int v, int p, int x){
      int tot = 0;
      for(int i = 0; i < G[v].size(); ++ i){
        if(G[v][i] == p)
          continue;
        go(G[v][i], v, x);
        tot += answer[G[v][i]] + 1;
      }
      answer[v] = max(0, tot - x);
    }
     
    int main(){
      scanf("%d", &n);
      for(int i = 1; i < n; ++ i){
        int x, y;
        scanf("%d %d", &x, &y);
        G[x].push_back(y);
        G[y].push_back(x);
      }
      int l = 0;
      int r = n;
      while(l < r){
        int mid = (l + r) / 2;
        go(1, 0, mid);
        if(answer[1])
          l = mid + 1;
        else
          r = mid;
      }
      printf("%d", l);
    }

Compilation message (stderr)

luk.cpp: In function 'void go(int, int, int)':
luk.cpp:11:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       for(int i = 0; i < G[v].size(); ++ i){
                      ~~^~~~~~~~~~~~~
luk.cpp: In function 'int main()':
luk.cpp:21:12: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
       scanf("%d", &n);
       ~~~~~^~~~~~~~~~
luk.cpp:24:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d", &x, &y);
         ~~~~~^~~~~~~~~~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 10 / 10
• Subtask 5: 10 / 10
• Subtask 6: 10 / 10
• Subtask 7: 10 / 10
• Subtask 8: 10 / 10
• Subtask 9: 10 / 10
• Subtask 10: 10 / 10