提出 #53136871 - AtCoder Beginner Contest 352

コンテスト時間: 2024-05-04 21:00:00+0900 ~ 2024-05-04 22:40:00+0900 (100分) AtCoderホームへ戻る

提出 #53136871

ソースコード拡げる

#include <bits/stdc++.h>

using namespace std;

using ll = long long;

const int N = 17;

int n,m,in[N],pos[N],has[N];
vector<pair<int,int> > g[N];
vector<vector<int> > al; 
vector<int> v;

void dfs(int x,int p,int fa){
	has[x]=1;
	while (v.size()<p+1+n){
		v.push_back(0);
	}
	v[p+n]=x;
	for (auto pr : g[x]){
		int y=pr.first,c=pr.second;
		if (!has[y]) dfs(y,c+p,x);
	}
}

int vis[1<<N][N];

int dfs2(int msk,int id){
//	cout<<msk<<","<<id<<endl;
	if (id==al.size()){
		return 1;
	}
	if (~vis[msk][id]){
		return vis[msk][id];
	}
	vis[msk][id]=0;
	int cnt=0;
	for (int st=0; st<n; st++){
		if (st+al[id].size()-1>=n){
			break;
		}
		bool fl=1;
		for (int j=0; j<al[id].size(); j++){
			fl&=(al[id][j]==0 || !(msk>>(st+j)&1));
		}
		if (fl){
			ll ms=msk;
			for (int k=0; k<al[id].size(); k++){
				if (al[id][k]){
					ms|=(1<<st+k);
				}
			}
			int t=dfs2(ms,id+1);
			if (!t){
				continue;
			} 
			cnt++;
			if (pos[al[id][0]]!=-2){
				for (int k=0; k<al[id].size(); k++){
					pos[al[id][k]]=-1;
				}
			}
			else{
				for (int k=0; k<al[id].size(); k++){
					pos[al[id][k]]=st+k;
				}
			}
		}
	}
	return vis[msk][id]=cnt;
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);

	cin>>n>>m;
	for (int i=1; i<=m; i++){
		int a,b,c;
		cin>>a>>b>>c;
		g[b].push_back({a,c});
		g[a].push_back({b,-c});
		in[a]++;
	}
	for (int i=1; i<=n; i++){
		if (!has[i]){
			v.clear();
			for (int j=1; j<=n; j++){
				v.push_back(0);
			}
			dfs(i,0,0);
			reverse(v.begin(),v.end());
			while (v.back()==0){
				v.pop_back();
			}
			reverse(v.begin(),v.end());
			al.push_back(v);
		//	for (auto u : v){
		//		cout<<u<<" ";
		//	}
		//	cout<<"\n";
		}
	}
	memset(vis,-1,sizeof vis);
	for (int i=1; i<=n; i++){
		pos[i]=-2;
	}
	dfs2(0,0);
	for (int i=1; i<=n; i++){
		cout<<(pos[i]==-1?-1:(pos[i]+1))<<" ";
	}
	cout<<"\n";
	return 0;
}

提出情報

提出日時	2024-05-04 22:34:03+0900
問題	F - Estimate Order
ユーザ	LessNaCl
言語	C++ 20 (gcc 12.2)
得点	0
コード長	1955 Byte
結果	WA
実行時間	16 ms
メモリ	12284 KiB

コンパイルエラー

Main.cpp: In function ‘void dfs(int, int, int)’:
Main.cpp:16:24: warning: comparison of integer expressions of different signedness: ‘std::vector<int>::size_type’ {aka ‘long unsigned int’} and ‘int’ [-Wsign-compare]
   16 |         while (v.size()<p+1+n){
      |                ~~~~~~~~^~~~~~
Main.cpp:14:26: warning: unused parameter ‘fa’ [-Wunused-parameter]
   14 | void dfs(int x,int p,int fa){
      |                      ~~~~^~
Main.cpp: In function ‘int dfs2(int, int)’:
Main.cpp:30:15: warning: comparison of integer expressions of different signedness: ‘int’ and ‘std::vector<std::vector<int> >::size_type’ {aka ‘long unsigned int’} [-Wsign-compare]
   30 |         if (id==al.size()){
      |             ~~^~~~~~~~~~~
Main.cpp:39:39: warning: comparison of integer expressions of different signedness: ‘std::vector<int>::size_type’ {aka ‘long unsigned int’} and ‘int’ [-Wsign-compare]
   39 |                 if (st+al[id].size()-1>=n){
      |                     ~~~~~~~~~~~~~~~~~~^~~
Main.cpp:43:32: warning: comparison of integer expressions of different signedness: ‘int’ and ‘std::vector<int>::size_type’ {aka ‘long unsigned int’} [-Wsign-compare]
   43 |                 for (int j=0; j<al[id].size(); j++){
      |                               ~^~~~~~~~~~~~~~
Main.cpp:48:40: warning: comparison of integer expressions of different signedness: ‘int’ and ‘std::vector<int>::size_type’ {aka ‘long unsigned int’} [-Wsign-compare]
   48 |                         for (int k=0; k<al[id].size(); k++){
      |                                       ~^~~~~~~~~~~~~~
Main.cpp:50:51: warning: suggest parentheses around ‘+’ inside ‘<<’ [-Wparentheses]
   50 |                                         ms|=(1<<st+k);
      |                                                 ~~^~
Main.cpp:59:48: warning: comparison of integer expressions of different signedness: ‘int’ and ‘std::vector<int>::size_type’ {aka ‘long unsigned int’} [-Wsign-compare]
   59 |                                 for (int k=0; k<al[id].size(); k++){
      |                                               ~^~~~~~~~~~~~~~
Main.cpp:64:48: warning: comparison of integer expressions of different signedness: ‘int’ and ‘std::vector<int>::size_type’ {aka ‘long unsigned int’} [-Wsign-compare]
   64 |                                 for (int k=0; k<al[id].size(); k++){
      |                                               ~^~~~~~~~~~~~~~

ジャッジ結果

セット名

Sample

All

得点 / 配点

0 / 0

0 / 525

結果

× 3

AC	× 58
WA	× 4

セット名	テストケース
Sample	sample00.txt, sample01.txt, sample02.txt
All	sample00.txt, sample01.txt, sample02.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, testcase56.txt, testcase57.txt, testcase58.txt

ケース名	結果	実行時間	メモリ
sample00.txt	AC	4 ms	12120 KiB
sample01.txt	AC	5 ms	12128 KiB
sample02.txt	AC	5 ms	12072 KiB
testcase00.txt	AC	5 ms	12144 KiB
testcase01.txt	AC	5 ms	12072 KiB
testcase02.txt	AC	4 ms	12188 KiB
testcase03.txt	AC	5 ms	12280 KiB
testcase04.txt	AC	4 ms	12064 KiB
testcase05.txt	AC	4 ms	12104 KiB
testcase06.txt	AC	5 ms	12276 KiB
testcase07.txt	AC	5 ms	12000 KiB
testcase08.txt	AC	5 ms	12272 KiB
testcase09.txt	AC	5 ms	12184 KiB
testcase10.txt	AC	5 ms	12140 KiB
testcase11.txt	AC	5 ms	12072 KiB
testcase12.txt	AC	4 ms	12132 KiB
testcase13.txt	AC	5 ms	12076 KiB
testcase14.txt	AC	4 ms	12284 KiB
testcase15.txt	AC	5 ms	12000 KiB
testcase16.txt	AC	5 ms	12132 KiB
testcase17.txt	WA	5 ms	12104 KiB
testcase18.txt	AC	5 ms	12128 KiB
testcase19.txt	AC	5 ms	12100 KiB
testcase20.txt	AC	4 ms	12076 KiB
testcase21.txt	AC	5 ms	12152 KiB
testcase22.txt	AC	5 ms	12248 KiB
testcase23.txt	AC	5 ms	12068 KiB
testcase24.txt	AC	5 ms	12152 KiB
testcase25.txt	WA	5 ms	12152 KiB
testcase26.txt	WA	5 ms	12144 KiB
testcase27.txt	AC	7 ms	12140 KiB
testcase28.txt	AC	5 ms	12148 KiB
testcase29.txt	AC	5 ms	12212 KiB
testcase30.txt	AC	8 ms	12132 KiB
testcase31.txt	AC	6 ms	12004 KiB
testcase32.txt	AC	8 ms	12208 KiB
testcase33.txt	AC	9 ms	12128 KiB
testcase34.txt	AC	10 ms	12124 KiB
testcase35.txt	AC	9 ms	12184 KiB
testcase36.txt	AC	11 ms	12144 KiB
testcase37.txt	AC	13 ms	12276 KiB
testcase38.txt	AC	13 ms	12064 KiB
testcase39.txt	WA	8 ms	12076 KiB
testcase40.txt	AC	13 ms	12104 KiB
testcase41.txt	AC	11 ms	12220 KiB
testcase42.txt	AC	15 ms	12124 KiB
testcase43.txt	AC	15 ms	12128 KiB
testcase44.txt	AC	14 ms	12008 KiB
testcase45.txt	AC	16 ms	12104 KiB
testcase46.txt	AC	15 ms	12124 KiB
testcase47.txt	AC	15 ms	12184 KiB
testcase48.txt	AC	7 ms	12144 KiB
testcase49.txt	AC	6 ms	12140 KiB
testcase50.txt	AC	10 ms	12188 KiB
testcase51.txt	AC	5 ms	12084 KiB
testcase52.txt	AC	5 ms	12128 KiB
testcase53.txt	AC	5 ms	12064 KiB
testcase54.txt	AC	5 ms	12188 KiB
testcase55.txt	AC	5 ms	12124 KiB
testcase56.txt	AC	5 ms	12080 KiB
testcase57.txt	AC	5 ms	12140 KiB
testcase58.txt	AC	5 ms	12092 KiB