| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 148126 | WhipppedCream | 열대 식물원 (Tropical Garden) (IOI11_garden) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#define ii pair<int, int>
#define X first
#define Y second
#define pb push_back
#define vi vector<int>
#define vii vector< pair<int, int> >
typedef long long ll;
using namespace std;
vector< ii > adj[150005];
bool cmp(ii A, ii B)
{
return A.second < B.second;
}
ii To[150005][2];
int deg[150005][2];
int Best[150005];
int Res[150005];
int cyc_id[150005][2];
int cyc_pos[150005][2];
vii cyc[150005];
int visit[150005][2];
int Steps[150005][2];
int realcycle[150005][2];
ii plaicycle[150005][2];
int cyc_cnt = 1;
int joe[150005][2];
int p;
ii find_paths(int u, int stat)
{
//printf("called %d %d\n", u, stat);
if(realcycle[u][stat])
{
return ii(-1, -1);
}
if(visit[u][stat] == 1)
{
return ii(u, stat);
}
if(joe[u][stat] == 1)
{
return ii(-1, -1);
}
joe[u][stat] = 1;
visit[u][stat] = 1;
ii tmp = To[u][stat];
ii res = find_paths(tmp.X, tmp.Y);
visit[u][stat] = 0;
if(res.X != -1)
{
cyc_id[u][stat] = cyc_cnt;
cyc_pos[u][stat] = cyc[cyc_cnt].size();
//printf("%d %d is in cycle\n", u, stat);
cyc[cyc_cnt].pb(ii(u, stat));
realcycle[u][stat] = 1;
if(res.X == u && res.Y == stat)
{
cyc_cnt++;
return ii(-1, -1);
}
return res;
}
Steps[u][stat] = Steps[To[u][stat].X][To[u][stat].Y]+1;
cyc_id[u][stat] = cyc_id[To[u][stat].X][To[u][stat].Y];
if(realcycle[To[u][stat].X][To[u][stat].Y]) plaicycle[u][stat] = To[u][stat];
else plaicycle[u][stat] = plaicycle[To[u][stat].X][To[u][stat].Y];
return ii(-1, -1);
}
ii dp[150005][2][20];
int findEnd(int start, int stat, int steps)
{
//printf("called %d %d %d\n", start, stat, steps);
int x = cyc_id[start][stat];
int y = cyc_id[p][0];
int z = cyc_id[p][1];
if(x != y && x != z) return -1;
if(realcycle[start][stat])
{
int id = cyc_id[start][stat];
int n = cyc[id].size();
int pos = n-1-cyc_pos[start][stat];
//printf("pos is %d\n", pos);
pos += steps;
pos %= n;
return cyc[id][pos].X;
}
else
{
//printf("not in cycle\n");
int x = Steps[start][stat];
if(x< steps)
{
return findEnd(plaicycle[start][stat].X, plaicycle[start][stat].Y, steps-x);
}
else
{
int cur_a = start;
int cur_b = stat;
for(int i = 17; i>= 0; i--)
{
if((1<<i) <= steps)
{
steps -= (1<<i);
int tmp_a = dp[cur_a][cur_b][i].X;
int tmp_b = dp[cur_a][cur_b][i].Y;
cur_a = tmp_a;
cur_b = tmp_b;
}
}
return cur_a;
}
}
}
int main()
{
memset(Res, -1, sizeof Res);
int n, m;
scanf("%d %d %d", &n, &m, &p);
for(int i = 0; i< m; i++)
{
int u, v;
scanf("%d %d", &u, &v);
adj[u].pb(ii(v, i));
adj[v].pb(ii(u, i));
}
for(int i = 0; i< n; i++)
{
sort(adj[i].begin(), adj[i].end(), cmp);
while((int) adj[i].size() > 2) adj[i].pop_back();
Best[i] = adj[i][0].X;
if((int) adj[i].size() == 2) Res[i] = adj[i][1].X;
//printf("%d: %d %d\n", i, Best[i], Res[i]);
}
for(int i = 0; i< n; i++)
{
int tmp = Best[i];
int aug;
if(Best[tmp] == i) aug = 1;
else aug = 0;
To[i][0]= ii(tmp, aug);
//if(i == 0) printf("dfjsklfjdsjkldjsfkdjslkfjdlsj %d %d\n", tmp, aug);
deg[tmp][aug]++;
int k = Res[i];
if(k == -1) k = Best[i];
if(Best[k] == i) aug = 1;
else aug = 0;
if(k == -1) k = Best[i];
To[i][1] = ii(k, aug);
deg[k][aug]++;
//if((tmp == 0 || k == 0) && aug == 0) printf("sfdksfjdasfjklsfjkl %d\n", i);
}
//printf("shittttttttt %d\n", deg[0][0]);
for(int i = 0; i< n; i++)
{
for(int j = 0; j< 2; j++)
{
if(joe[i][j] == 0)
{
//printf("dfs at %d %d\n", i, j);
find_paths(i, j);
}
}
}
for(int i = 1; i< cyc_cnt; i++)
{
reverse(cyc[i].begin(), cyc[i].end());
}
/*printf("---paths\n");
printf("paths count = %d\n", paths_cnt);
for(int i = 1; i< paths_cnt; i++)
{
printf("[[[[[[[[[[[[[[[[[[[[[%d]]]]]]]]]]]]]]]]]]]]", i);
for(int j = 0; j< (int) paths[i].size(); j++)
{
printf("(%d, %d)", paths[i][j].X, paths[i][j].Y);
}
printf("-------------------------\n");
}*/
/*printf("---cycles\n");
for(int i = 1; i< cyc_cnt; i++)
{
for(int j = 0; j< (int) cyc[i].size(); j++)
{
printf("(%d, %d)", cyc[i][j].X, cyc[i][j].Y);
}
printf("-------------------------------------------\n");
}
printf("Plaicycle\n");
*/
/*for(int i = 0; i< n; i++)
{
for(int j = 0; j< 2; j++)
{
printf("%d %d: %d %d (%d)\n", i, j, plaicycle[i][j].X, plaicycle[i][j].Y, Steps[i][j]);
}
}*/
for(int i = 0; i< n; i++)
{
for(int j = 0; j< 2; j++)
{
if(realcycle[i][j]) dp[i][j][0] = ii(i, j);
else dp[i][j][0] = To[i][j];
}
}
for(int k = 1; k< 18; k++)
{
for(int i= 0; i< n; i++)
{
for(int j= 0; j< 2; j++)
{
int a = dp[i][j][k-1].X;
int b = dp[i][j][k-1].Y;
dp[i][j][k] = dp[a][b][k-1];
}
}
}
int tt;
scanf("%d", &tt);
while(tt--)
{
int k;
scanf("%d", &k);
int ans = 0;
for(int i = 0; i< n; i++)
{
int res = findEnd(i, 0, k);
//printf("%d %d ends at %d\n", i, 0, res);
if(res == p)
{
ans++;
}
}
printf("%d ", ans);
}
return 0;
}