Submission #198439

#	Time	Username	Problem	Language	Result	Execution time	Memory
198439		model_code	Travels (LMIO17_keliones)	C++17	100 / 100	230 ms	18852 KiB

keliones

#include <stdio.h>
#include <assert.h>
#include <vector>
#include <algorithm>

using namespace std;

typedef long long ll;

const ll MOD = 1000000000 + 7;

const int MAXN = 2 * 100000 + 100; 


vector<int> E[MAXN][2]; // E[i][0] saugo išimtas iš grafo briaunas, kurios prasideda viršūnėje i, 
                        // o E[i][1] saugo išimtas iš grafo briaunas, kurios baigiasi viršūnėje i.
ll W[MAXN]; // Viršūnių svoriai.

ll A[MAXN]; // A[i] - kelių, pasibaigiančių viršūnėje i, skaičius.
ll B[MAXN]; // B[i] - kelių, prasidedančių viršūnėje i, skaičius.

int N, M;

int main() {
  scanf("%d %d", &N, &M);

  for (int i = 0;i < N;++i) {
    scanf("%lld", &W[i]);
  }

  for (int i = 0;i < M;++i) {
    int a, b;
    scanf("%d %d", &a, &b);
    
    // Numeruojame nuo 0.
    a--;
    b--;

    E[a][0].push_back(b);
    E[b][1].push_back(a);
  }
  
  // Kelių, pasibaigiančių nulinėje viršūnėje, skaičius yra 0, nes kelias turi turėti bent dvi viršūnes.
  A[0] = 0;
  
  // A[i] = (A[0] + 1) + (A[1] + 1) + .. + (A[i - 1] + 1) - (A[x1] + 1) - (A[x2] + 1) - .. - (A[xk] + 1)
  // kur x1, x2, .., xk yra viršūnės, iš kurių briaunos į viršūnę i neina, t.y. buvo išimtos.
  // Kintamajame s saugome (A[0] + 1) + (A[1] + 1) + .. + (A[i - 1] + 1) reikšmę.
  ll s = 1;

  for (int i = 1;i < N;++i) {
    A[i] = s;

    for (int j = 0;j < E[i][1].size();++j) {
      int u = E[i][1][j];

      A[i] = (A[i] - A[u] - 1) % MOD;
    }
    
    s = (s + A[i] + 1) % MOD;
  }
  
  // Analogiškai, B[i] = (B[N - 1] + 1) + .. + (B[i + 1] + 1) - (B[x1] + 1) - .. - (B[xk] + 1),
  // kur x1, .., xk yra viršūnės, į kurias briaunos iš viršūnės i nėra, t.y. buvo išimtos.
  B[N - 1] = 0;
  s = 1;

  for (int i = N - 2;i >= 0;--i) {
    B[i] = s;

    for (int j = 0;j < E[i][0].size();++j) {
      int u = E[i][0][j];

      B[i] = (B[i] - B[u] - 1) % MOD;
    }

    s = (s + B[i] + 1) % MOD;
  }
  
  // Jei A[i] - visų kelių, pasibaigiančių viršūnėje i, skaičius, o B[i] - visų kelių, prasidedančių viršūnėje i, skaičius, tai
  // A[i] * B[i] + A[i] + B[i] - visų kelių einančių per viršūnę i skaičius.
  // Todėl atsakymas yra suma per visus i W[i] * (A[i] * B[i] + A[i] + B[i])
  ll answer = 0;
  
  // Išnaudojame tapatybę A[i] * B[i] + A[i] + B[i] = (A[i] + 1) * (B[i] + 1) - 1.
  for (int i = 0;i < N;++i) {
    answer = ((W[i] * ((A[i] + 1) * (B[i] + 1) % MOD) % MOD) + answer) % MOD;
  }

  for (int i = 0;i < N;++i) {
    answer = (answer - W[i]) % MOD;
  }
  answer = (answer + MOD) % MOD;
  printf("%lld\n", answer);
  return 0;
}

Compilation message (stderr)

keliones.cpp: In function 'int main()':
keliones.cpp:54:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int j = 0;j < E[i][1].size();++j) {
                    ~~^~~~~~~~~~~~~~~~
keliones.cpp:71:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int j = 0;j < E[i][0].size();++j) {
                    ~~^~~~~~~~~~~~~~~~
keliones.cpp:25:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d", &N, &M);
   ~~~~~^~~~~~~~~~~~~~~~~
keliones.cpp:28:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%lld", &W[i]);
     ~~~~~^~~~~~~~~~~~~~~
keliones.cpp:33:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d", &a, &b);
     ~~~~~^~~~~~~~~~~~~~~~~

• Subtask 1: 8 / 8
• Subtask 2: 12 / 12
• Subtask 3: 25 / 25
• Subtask 4: 55 / 55