Submission #63029535

Source Code Expand

#include<bits/stdc++.h>
using namespace std;
int n,dis[105][105],x[1000005],y[1000005],l=1,r;
char s[105][105];
vector<int>con[105][26],conr[105][26];
void add(int a,int b,int c){dis[a][b]=c,x[++r]=a,y[r]=b;}
int main(){
	memset(dis,0x3f,sizeof(dis));
	scanf("%d",&n);
	for(int i=1;i<=n;i++)add(i,i,0);
	for(int i=1;i<=n;i++){
		scanf("%s",s[i]+1);
		for(int j=1;j<=n;j++)if(s[i][j]!='-'){
			int x=s[i][j]-'a';
			con[i][x].push_back(j),conr[j][x].push_back(i);
			if(i!=j)add(i,j,1);
		}
	}
	while(l<=r){
		int a=x[l],b=y[l++];
		for(int i=0;i<26;i++)for(int na:conr[a][i])for(int nb:con[b][i])
			if(dis[na][nb]>dis[a][b]+1)add(na,nb,dis[a][b]+2);
	}
	for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)printf("%d%c",dis[i][j]>1e9?-1:dis[i][j]," \n"[j==n]);
}

Submission Info

Submission Time
Task E - Palindromic Shortest Path
User zeyuanliu
Language C++ 20 (gcc 12.2)
Score 450
Code Size 779 Byte
Status AC
Exec Time 42 ms
Memory 4508 KiB

Compile Error

Main.cpp: In function ‘int main()’:
Main.cpp:9:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
    9 |         scanf("%d",&n);
      |         ~~~~~^~~~~~~~~
Main.cpp:12:22: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   12 |                 scanf("%s",s[i]+1);
      |                 ~~~~~^~~~~~~~~~~~~

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 450 / 450
Status
AC × 2
AC × 58
Set Name Test Cases
Sample sample00.txt, sample01.txt
All sample00.txt, sample01.txt, testcase00.txt, testcase01.txt, testcase02.txt, testcase03.txt, testcase04.txt, testcase05.txt, testcase06.txt, testcase07.txt, testcase08.txt, testcase09.txt, testcase10.txt, testcase11.txt, testcase12.txt, testcase13.txt, testcase14.txt, testcase15.txt, testcase16.txt, testcase17.txt, testcase18.txt, testcase19.txt, testcase20.txt, testcase21.txt, testcase22.txt, testcase23.txt, testcase24.txt, testcase25.txt, testcase26.txt, testcase27.txt, testcase28.txt, testcase29.txt, testcase30.txt, testcase31.txt, testcase32.txt, testcase33.txt, testcase34.txt, testcase35.txt, testcase36.txt, testcase37.txt, testcase38.txt, testcase39.txt, testcase40.txt, testcase41.txt, testcase42.txt, testcase43.txt, testcase44.txt, testcase45.txt, testcase46.txt, testcase47.txt, testcase48.txt, testcase49.txt, testcase50.txt, testcase51.txt, testcase52.txt, testcase53.txt, testcase54.txt, testcase55.txt
Case Name Status Exec Time Memory
sample00.txt AC 1 ms 3736 KiB
sample01.txt AC 1 ms 3852 KiB
testcase00.txt AC 1 ms 3840 KiB
testcase01.txt AC 1 ms 3704 KiB
testcase02.txt AC 2 ms 3828 KiB
testcase03.txt AC 10 ms 4304 KiB
testcase04.txt AC 1 ms 3764 KiB
testcase05.txt AC 1 ms 3920 KiB
testcase06.txt AC 2 ms 3860 KiB
testcase07.txt AC 1 ms 4048 KiB
testcase08.txt AC 1 ms 4032 KiB
testcase09.txt AC 2 ms 3796 KiB
testcase10.txt AC 1 ms 4048 KiB
testcase11.txt AC 1 ms 3912 KiB
testcase12.txt AC 1 ms 4044 KiB
testcase13.txt AC 1 ms 4076 KiB
testcase14.txt AC 1 ms 3944 KiB
testcase15.txt AC 2 ms 3920 KiB
testcase16.txt AC 1 ms 3716 KiB
testcase17.txt AC 2 ms 3912 KiB
testcase18.txt AC 1 ms 3760 KiB
testcase19.txt AC 2 ms 4012 KiB
testcase20.txt AC 1 ms 4024 KiB
testcase21.txt AC 6 ms 4220 KiB
testcase22.txt AC 4 ms 4156 KiB
testcase23.txt AC 14 ms 4328 KiB
testcase24.txt AC 3 ms 3928 KiB
testcase25.txt AC 42 ms 4396 KiB
testcase26.txt AC 1 ms 4044 KiB
testcase27.txt AC 4 ms 4100 KiB
testcase28.txt AC 3 ms 4136 KiB
testcase29.txt AC 13 ms 4444 KiB
testcase30.txt AC 4 ms 4044 KiB
testcase31.txt AC 17 ms 4284 KiB
testcase32.txt AC 2 ms 3892 KiB
testcase33.txt AC 4 ms 4336 KiB
testcase34.txt AC 2 ms 3924 KiB
testcase35.txt AC 13 ms 4404 KiB
testcase36.txt AC 5 ms 4196 KiB
testcase37.txt AC 18 ms 4288 KiB
testcase38.txt AC 2 ms 4036 KiB
testcase39.txt AC 4 ms 4108 KiB
testcase40.txt AC 8 ms 4208 KiB
testcase41.txt AC 13 ms 4428 KiB
testcase42.txt AC 4 ms 3924 KiB
testcase43.txt AC 18 ms 4508 KiB
testcase44.txt AC 2 ms 3880 KiB
testcase45.txt AC 2 ms 3828 KiB
testcase46.txt AC 1 ms 3972 KiB
testcase47.txt AC 4 ms 4036 KiB
testcase48.txt AC 5 ms 4256 KiB
testcase49.txt AC 7 ms 4116 KiB
testcase50.txt AC 4 ms 4256 KiB
testcase51.txt AC 9 ms 4164 KiB
testcase52.txt AC 2 ms 3912 KiB
testcase53.txt AC 13 ms 4452 KiB
testcase54.txt AC 11 ms 4160 KiB
testcase55.txt AC 20 ms 4364 KiB