| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 218895 | FieryPhoenix | Tropical Garden (IOI11_garden) | C++11 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
typedef long long ll;
typedef long double ld;
#define INF 2001001001
#define MOD 1000000007
#define f first
#define s second
int N,M,P;
int x[150001],y[150001];
vector<pair<int,int>>adj[150001];
vector<int>adj2[300001];
int dis[300001][2],size[2];
int minEdge[300001];
void dfs(int node, int source, bool b){
for (int x:adj2[node]){
if (x==source){
size[b]=dis[node][b]+1;
return;
}
if (dis[x][b]==0){
dis[x][b]=dis[node][b]+1;
dfs(x,source,b);
}
}
}
void count_routes(int N, int M, int P, vector<pair<int,int>>R, int Q, vector<int>G){
for (int i=0;i<M;i++){
x[i]=R[i].first;
y[i]=R[i].second;
adj[x[i]].push_back({i,y[i]});
adj[y[i]].push_back({i,x[i]});
}
for (int i=0;i<N;i++){
sort(adj[i].begin(),adj[i].end());
minEdge[i]=adj[i][0].first;
}
for (int i=0;i<N;i++){
if ((int)adj[i].size()==1){
adj2[adj[i][0].s+N*(adj[i][0].f==minEdge[adj[i][0].s])].push_back(i);
adj2[adj[i][0].s+N*(adj[i][0].f==minEdge[adj[i][0].s])].push_back(i+N);
}
else{
adj2[adj[i][0].s+N*(adj[i][0].f==minEdge[adj[i][0].s])].push_back(i);
adj2[adj[i][1].s+N*(adj[i][1].f==minEdge[adj[i][1].s])].push_back(i+N);
}
}
dfs(P,P,0);
dfs(P+N,P+N,1);
for (int i=0;i<Q;i++){
int K=G[i];
int ans=0;
for (int j=0;j<N;j++){
bool good=false;
for (int k=0;k<2;k++){
if (dis[j][k]!=0){
if (size[k]==0){
if (dis[j][k]==K)
good=true;
}
else{
if (K-dis[j][k]>=0 && (K-dis[j][k])%size[k]==0)
good=true;
}
}
}
ans+=good;
}
answer(ans);
}
}