| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 218899 | FieryPhoenix | 열대 식물원 (Tropical Garden) (IOI11_garden) | C++11 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#include "garden.h"
#include "gardenlib.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, int R[][2], int Q, 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);
}
}