이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#include "garden.h"
#include "gardenlib.h"
#define DIM 300010
#define INF 2000000000
using namespace std;
int nxt[DIM],dist[DIM],dist2[DIM];
vector <pair<int,int> > L[DIM];
vector <int> edg[DIM];
deque <int> c;
/*void answer (int n){
cout<<n<<"\n";
}*/
void bfs (int start, int n, int dist[]){
int i;
for (i=1;i<=2*n;i++)
dist[i] = INF;
c.clear();
c.push_back(start);
dist[start] = 0;
while (!c.empty()){
int nod = c.front();
c.pop_front();
for (auto vecin : edg[nod]){
if (dist[vecin] == INF){
dist[vecin] = 1 + dist[nod];
c.push_back(vecin);
}}}}
void count_routes (int n, int m, int dest, int r[][2], int q, int g[]){
int i,j;
for (i=0;i<m;i++){
int x = r[i][0] + 1, y = r[i][1] + 1;
L[x].push_back(make_pair(i,y));
L[y].push_back(make_pair(i,x));
}
dest++;
for (i=1;i<=n;i++)
sort (L[i].begin(),L[i].end());
for (i=1;i<=n;i++){
/// duc muchia catre cea mai buna varianta
j = L[i][0].second;
if (L[j][0].second != i){
edg[j].push_back(i); /// graful o sa fie pe invers
nxt[i] = j;
} else {
edg[j+n].push_back(i);
nxt[i] = j+n;
}
/// a doua muchie
if (L[i].size() >= 2){
j = L[i][1].second;
if (L[j][0].second != i){
edg[j].push_back(i+n);
nxt[i+n] = j;
} else {
edg[j+n].push_back(i+n);
nxt[i+n] = j+n;
}
} else {
j = L[i][0].second;
if (L[j][0].second != i){
edg[j].push_back(i+n);
nxt[i+n] = j;
} else {
edg[j+n].push_back(i+n);
nxt[i+n] = j+n;
}}}
bfs (dest,n,dist);
bfs (dest+n,n,dist2);
//for (i=1;i<=2*n;i++)
// cout<<dist[i]<<"\n";
/// am doua variante de a ajunge la destinatie => doua cicluri posibile
int lg = dist[nxt[dest]] + 1;
int lg2 = dist2[nxt[dest+n]] + 1;
for (i=0;i<q;i++){
int k = g[i], sol = 0;
for (j=1;j<=n;j++)
if ( ((k >= dist[j]) && (k - dist[j]) % lg == 0) || (k >= dist2[j] && (k - dist2[j]) % lg2 == 0) )
sol++;
answer(sol);
}
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |