# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
400481 | Lawliet | Special graph (IZhO13_specialg) | C++17 | 158 ms | 21576 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;
typedef long long int lli;
const int LOG = 20;
const int MAXN = 100010;
const int INF = 1000000010;
int n, qtdQueries;
int ans[MAXN];
int mn[LOG][MAXN];
int tab[LOG][MAXN];
int inDegree[MAXN];
int type[MAXN], a[MAXN], b[MAXN];
int posCycle[MAXN];
int indCycle[MAXN], szCycle[MAXN];
int treeDepth[MAXN], indTree[MAXN];
bool mark[MAXN];
vector<int> ord;
queue<int> q;
void add(int cur)
{
q.push( cur );
mark[cur] = true;
}
void topologicalSorting()
{
for(int i = 1 ; i <= n ; i++)
inDegree[ tab[0][i] ]++;
for(int i = 1 ; i <= n ; i++)
if( inDegree[i] == 0 ) add( i );
while( !q.empty() )
{
int cur = q.front();
q.pop();
ord.push_back( cur );
if( --inDegree[ tab[0][cur] ] == 0 )
add( tab[0][cur] );
}
int qtdCycles = 0;
for(int i = 1 ; i <= n ; i++)
{
if( mark[i] ) continue;
int cur = i, pos = 0;
qtdCycles++;
while( !mark[cur] )
{
mark[cur] = true;
szCycle[qtdCycles]++;
posCycle[cur] = pos++;
indCycle[cur] = qtdCycles;
cur = tab[0][cur];
}
}
int qtdTrees = 0;
indTree[0] = -1;
while( !ord.empty() )
{
int cur = ord.back();
ord.pop_back();
if( indCycle[ tab[0][cur] ] != 0 ) indTree[cur] = ++qtdTrees;
else indTree[cur] = indTree[ tab[0][cur] ];
treeDepth[cur] = treeDepth[ tab[0][cur] ] + 1;
}
}
int jump(int node, int k)
{
for(int i = 0 ; i < LOG ; i++)
if( k & (1 << i) ) node = tab[i][node];
return node;
}
int getMin(int node, int k)
{
int ans = INF;
for(int i = 0 ; i < LOG ; i++)
{
if( k & (1 << i) )
{
ans = min( ans , mn[i][node] );
node = tab[i][node];
}
}
return ans;
}
void solveTestCase()
{
scanf("%d",&n);
for(int i = 1 ; i <= n ; i++)
scanf("%d",&tab[0][i]);
for(int i = 1 ; i <= n ; i++)
mn[0][i] = INF;
for(int i = 0 ; i < LOG ; i++)
mn[i][0] = INF;
scanf("%d",&qtdQueries);
for(int i = 1 ; i <= qtdQueries ; i++)
{
scanf("%d",&type[i]);
if( type[i] == 1 )
{
scanf("%d",&a[i]);
mn[0][ a[i] ] = i;
}
if( type[i] == 2 ) scanf("%d %d",&a[i],&b[i]);
}
for(int k = 1 ; k < LOG ; k++)
{
for(int i = 1 ; i <= n ; i++)
{
int jump = tab[k - 1][i];
tab[k][i] = tab[k - 1][jump];
mn[k][i] = min( mn[k - 1][i] , mn[k - 1][jump] );
}
}
topologicalSorting();
for(int i = 1 ; i <= qtdQueries ; i++)
{
if( type[i] == 1 ) continue;
int dist = 0;
int A = a[i], B = b[i];
if( indTree[A] != 0 && indTree[A] == indTree[B] )
{
int jumpA = jump( A , treeDepth[A] - treeDepth[B] );
if( jumpA != B ) ans[i] = -1;
else ans[i] = treeDepth[A] - treeDepth[B];
continue;
}
int t = jump( A , MAXN );
int root = jump( A , treeDepth[A] );
if( t == 0 || indCycle[t] != indCycle[B] )
{
ans[i] = -1;
continue;
}
ans[i] = posCycle[B] - posCycle[root];
if( ans[i] < 0 ) ans[i] += szCycle[ indCycle[root] ];
ans[i] += treeDepth[A];
}
for(int i = 1 ; i <= qtdQueries ; i++)
{
if( type[i] == 1 ) continue;
if( ans[i] == -1 ) printf("-1\n");
else if( getMin( a[i] , ans[i] ) < i ) printf("-1\n");
else printf("%d\n",ans[i]);
}
}
int main()
{
int t = 1;
// scanf("%d",&t);
while( t-- )
solveTestCase();
}
컴파일 시 표준 에러 (stderr) 메시지
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |