提出 #1996809

ソースコード 拡げる

#include<bits/stdc++.h>
#define L long long
#define pb push_back
#define pi pair<int,int>
#define pii pair<pair<int,int>,int>
#define aa first
#define bb second
#define xx aa.aa
#define yy aa.bb
#define zz bb
#define mp make_pair
#define mpp(a,b,c) mp(mp(a,b),c)
using namespace std;
int n,f[200010],x[200010],b[200010],c[200010],w[200010],p;
vector<int> a[200010];
inline void get(int i)
{
	int j;
	for(auto j:a[i])
	  w[f[j]]++;
	for(j=0;w[j];j++);
	f[i]=j;
	for(auto j:a[i])
	  w[f[j]]--;
}
inline void get2(int i)
{
	int j;
	for(auto j:a[i])
	  w[f[j]]++;
	for(j=0;w[j];j++);
	for(j++;w[j];j++);
	f[i]=j;
	for(auto j:a[i])
	  w[f[j]]--;
}
inline void dfs(int i)
{
	for(auto j:a[i])
	  dfs(j);
	get(i);
}
int main()
{
	//freopen(".in","r",stdin);
	//freopen(".out","w",stdout);
	int i;
	scanf("%d",&n);
	for(i=1;i<=n;i++)
	  {
	   scanf("%d",&x[i]);
	   a[x[i]].pb(i);
	  }
	for(i=1;b[i]<2;i=x[i])
	  {
	   b[i]++;
	   if(b[i]==2)
	     c[++p]=i;
	  }
	for(i=1;i<=p;i++)
	  for(auto j:a[c[i]])
	    if(b[j]<2)
	      dfs(j);
	f[c[p]]=n+5;
	get(c[1]);
	for(i=2;i<=p;i++)
	  get(c[i]);
	i=f[c[1]];
	get(c[1]);
	if(i==f[c[1]])
	  {
	   printf("POSSIBLE\n");
	   return 0;
	  }
	f[c[p]]=n+5;
	get2(c[1]);
	for(i=2;i<=p;i++)
	  get(c[i]);
	i=f[c[1]];
	get(c[1]);
	if(i==f[c[1]])
	  printf("POSSIBLE\n");
	else
	  printf("IMPOSSIBLE\n");
	return 0;
}

提出情報

提出日時
問題 F - Namori Grundy
ユーザ fateice
言語 C++14 (GCC 5.4.1)
得点 800
コード長 1434 Byte
結果 AC
実行時間 56 ms
メモリ 14080 KiB

コンパイルエラー

./Main.cpp: In function ‘int main()’:
./Main.cpp:48:16: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&n);
                ^
./Main.cpp:51:22: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d",&x[i]);
                      ^

ジャッジ結果

セット名 Sample All
得点 / 配点 0 / 0 800 / 800
結果
AC × 4
AC × 68
セット名 テストケース
Sample example0, example1, example2, example3
All example0, example1, example2, example3, loop0, loop1, loop10, loop11, loop12, loop13, loop14, loop15, loop16, loop17, loop18, loop19, loop2, loop3, loop4, loop5, loop6, loop7, loop8, loop9, loopex0, loopex1, loopex10, loopex11, loopex12, loopex13, loopex14, loopex15, loopex16, loopex17, loopex18, loopex19, loopex2, loopex20, loopex21, loopex22, loopex23, loopex3, loopex4, loopex5, loopex6, loopex7, loopex8, loopex9, rand0, rand1, rand2, rand3, rand4, rand5, rand6, rand7, rand8, rand9, small0, small1, small2, small3, small4, small5, small6, small7, small8, small9
ケース名 結果 実行時間 メモリ
example0 AC 4 ms 8448 KiB
example1 AC 4 ms 8448 KiB
example2 AC 4 ms 8448 KiB
example3 AC 4 ms 8448 KiB
loop0 AC 42 ms 11648 KiB
loop1 AC 45 ms 11648 KiB
loop10 AC 43 ms 11648 KiB
loop11 AC 43 ms 11648 KiB
loop12 AC 42 ms 11648 KiB
loop13 AC 43 ms 11648 KiB
loop14 AC 42 ms 11648 KiB
loop15 AC 43 ms 11648 KiB
loop16 AC 43 ms 11648 KiB
loop17 AC 43 ms 11648 KiB
loop18 AC 43 ms 11648 KiB
loop19 AC 42 ms 11648 KiB
loop2 AC 44 ms 11648 KiB
loop3 AC 44 ms 11648 KiB
loop4 AC 44 ms 11648 KiB
loop5 AC 43 ms 11648 KiB
loop6 AC 44 ms 11648 KiB
loop7 AC 43 ms 11648 KiB
loop8 AC 42 ms 11648 KiB
loop9 AC 46 ms 11648 KiB
loopex0 AC 44 ms 11776 KiB
loopex1 AC 43 ms 11648 KiB
loopex10 AC 43 ms 11648 KiB
loopex11 AC 43 ms 11648 KiB
loopex12 AC 42 ms 11648 KiB
loopex13 AC 42 ms 11648 KiB
loopex14 AC 42 ms 11648 KiB
loopex15 AC 43 ms 11648 KiB
loopex16 AC 43 ms 11776 KiB
loopex17 AC 43 ms 11648 KiB
loopex18 AC 44 ms 11776 KiB
loopex19 AC 42 ms 11648 KiB
loopex2 AC 42 ms 11648 KiB
loopex20 AC 42 ms 11648 KiB
loopex21 AC 43 ms 11776 KiB
loopex22 AC 43 ms 11776 KiB
loopex23 AC 43 ms 11648 KiB
loopex3 AC 43 ms 11648 KiB
loopex4 AC 45 ms 11648 KiB
loopex5 AC 52 ms 11776 KiB
loopex6 AC 42 ms 11648 KiB
loopex7 AC 44 ms 11776 KiB
loopex8 AC 43 ms 11776 KiB
loopex9 AC 44 ms 11776 KiB
rand0 AC 16 ms 9344 KiB
rand1 AC 23 ms 9728 KiB
rand2 AC 7 ms 8960 KiB
rand3 AC 41 ms 11520 KiB
rand4 AC 56 ms 14080 KiB
rand5 AC 25 ms 9984 KiB
rand6 AC 12 ms 9344 KiB
rand7 AC 6 ms 8576 KiB
rand8 AC 37 ms 11008 KiB
rand9 AC 5 ms 8704 KiB
small0 AC 4 ms 8448 KiB
small1 AC 4 ms 8448 KiB
small2 AC 4 ms 8448 KiB
small3 AC 4 ms 8448 KiB
small4 AC 4 ms 8448 KiB
small5 AC 4 ms 8448 KiB
small6 AC 4 ms 8448 KiB
small7 AC 4 ms 8448 KiB
small8 AC 4 ms 8448 KiB
small9 AC 4 ms 8448 KiB