結果
問題 | No.2630 Colorful Vertices and Cheapest Paths |
ユーザー | PersistentLife |
提出日時 | 2024-02-16 21:34:28 |
言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 571 ms / 2,500 ms |
コード長 | 1,834 bytes |
コンパイル時間 | 1,720 ms |
コンパイル使用メモリ | 169,820 KB |
実行使用メモリ | 83,832 KB |
最終ジャッジ日時 | 2024-02-16 21:34:41 |
合計ジャッジ時間 | 10,786 ms |
ジャッジサーバーID (参考情報) |
judge13 / judge14 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 211 ms
83,692 KB |
testcase_01 | AC | 477 ms
83,800 KB |
testcase_02 | AC | 540 ms
83,824 KB |
testcase_03 | AC | 27 ms
83,480 KB |
testcase_04 | AC | 28 ms
83,472 KB |
testcase_05 | AC | 27 ms
83,480 KB |
testcase_06 | AC | 132 ms
83,640 KB |
testcase_07 | AC | 505 ms
83,832 KB |
testcase_08 | AC | 518 ms
83,816 KB |
testcase_09 | AC | 522 ms
83,832 KB |
testcase_10 | AC | 544 ms
83,832 KB |
testcase_11 | AC | 530 ms
83,832 KB |
testcase_12 | AC | 571 ms
83,832 KB |
testcase_13 | AC | 561 ms
83,832 KB |
testcase_14 | AC | 551 ms
83,832 KB |
testcase_15 | AC | 162 ms
83,760 KB |
testcase_16 | AC | 161 ms
83,760 KB |
testcase_17 | AC | 160 ms
83,760 KB |
testcase_18 | AC | 232 ms
83,676 KB |
testcase_19 | AC | 360 ms
83,792 KB |
testcase_20 | AC | 316 ms
83,760 KB |
testcase_21 | AC | 398 ms
83,832 KB |
ソースコード
/* Things to notice: 1. do not calculate useless values 2. do not use similar names Things to check: 1. submit the correct file 2. time (it is log^2 or log) 3. memory 4. prove your naive thoughts 5. long long 6. corner case like n=0,1,inf or n=m 7. check if there is a mistake in the ds or other tools you use 8. fileio in some oi-contest 9. module on time 10. the number of a same divisor in a math problem 11. multi-information and queries for dp and ds problems */ #include<bits/stdc++.h> using namespace std; #define int long long #define fi first #define se second #define pii pair<long long,long long> #define mp make_pair #define pb push_back const int mod=998244353; const int inf=0x3f3f3f3f; const int INF=1e18; struct DSU { int fa[10005]; void init() { for(int i=1;i<=10000;i++) fa[i]=i; } int find(int x) { if(fa[x]==x) return x; return fa[x]=find(fa[x]); } void merge(int x,int y) { int xx=find(x),yy=find(y); if(xx!=yy) fa[xx]=yy; } }dsu[1<<10]; int n,m; int U[10005],V[10005]; int col[10005],sum[1<<10]; int W[10]; void solve() { cin>>n>>m; for(int i=1;i<=m;i++) cin>>U[i]>>V[i]; for(int i=1;i<=n;i++) cin>>col[i],col[i]--; for(int i=0;i<10;i++) cin>>W[i]; for(int mask=0;mask<(1<<10);mask++) { for(int j=0;j<10;j++) if(mask&(1<<j)) sum[mask]+=W[j]; dsu[mask].init(); for(int i=1;i<=m;i++) { int u=U[i],v=V[i]; if((mask&(1<<col[u]))&&(mask&(1<<col[v]))) dsu[mask].merge(u,v); } } int Q; cin>>Q; while(Q--) { int u,v; cin>>u>>v; int ans=INF; for(int mask=0;mask<(1<<10);mask++) if((mask&(1<<col[u]))&&(mask&(1<<col[v]))) { if(dsu[mask].find(u)==dsu[mask].find(v)) ans=min(ans,sum[mask]); } if(ans==INF) ans=-1; cout<<ans<<"\n"; } } signed main() { ios::sync_with_stdio(0); cin.tie(0); int _=1; // cin>>_; while(_--) solve(); return 0; }