Azusamitsusa

2021 济南 南京 铁牌

3149

lamentropetion
Koschei
ღSupperღ
nope_ck
ruiOne
say1ka

zmzmc
Patricky

Asuka_4
mnicd

_marble_
an_87
Pein
y0ung

Azusamitsusa
1个月前

//郑老师和na姐一样可爱^ ^
#include <bits/stdc++.h>
using namespace std;
const int N = 1e6+10;
const int M = 998244353;
const int mod = 998244353;
#define int long long
int up(int a,int b){return a<0?a/b:(a+b-1)/b;}
#define endl '\n'
#define all(x) (x).begin(),(x).end()
#define YES cout<<"YES"<<endl;
#define NO cout<<"NO"<<endl;
#define _ 0
#define db double
#define pi acos(-1)
#define INF 0x3f3f3f3f3f3f3f3f
#define PII pair<int,int>
#define fast ios::sync_with_stdio(false);cin.tie(nullptr);
vector<int>g[500010];
int n,m,depth[500010],fa[500010][21],dp[500010],ans;
void bfs(int x){
memset(depth,0x3f3f,sizeof depth);
queue<int>q;q.push(x);
depth[0]=0,depth[x]=1;
while(q.size()){
auto u=q.front();q.pop();
for(auto v:g[u]){
if(depth[v]>depth[u]+1){
depth[v]=depth[u]+1;
q.push(v);
fa[v][0]=u;
for(int k=1;k<=19;k++)fa[v][k]=fa[fa[v][k-1]][k-1];
}
}
}
}
int lca(int a,int b){
if(depth[a]>depth[b])swap(a,b);
for(int k=19;k>=0;k--)if(depth[fa[b][k]]>=depth[a])b=fa[b][k];
if(a==b)return a;
for(int k=19;k>=0;k--){
if(fa[a][k]!=fa[b][k]){
a=fa[a][k];
b=fa[b][k];
}
}
return fa[a][0];
}
int dis(int a, int b){
int c = lca(a, b);
return abs(depth[c]-depth[a]) + abs(depth[c]-depth[b]);
}
void dfs(int u){
for(auto v:g[u]){
if(depth[v]<depth[u])continue;
dfs(v);
dp[u]+=dp[v];
if(!dp[v])ans+=m;
else if(dp[v]==1)ans++;
}
}
void solve(){
cin>>n>>m;
for(int i=1;i<n;i++){
int u,v;cin>>u>>v;
g[u].push_back(v);
g[v].push_back(u);
}
bfs(1);
for(int i=0;i<m;i++){
int u,v;cin>>u>>v;
int f=lca(u,v);
dp[f]-=2;
dp[u]++,dp[v]++;
}
dfs(1);
cout<<ans<<endl;
}
signed main(){
fast
int t;t=1;//cin>>t；
while(t--) {
solve();
}
return ~~(0^_^0);
}
//注意代码要放在两组三个点之间，才可以正确显示代码高亮哦~

Azusamitsusa
1个月前
//Ö£ÀÏÊ¦ºÍna½ãÒ»Ñù¿É°®^ ^
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5+10;
const int M = 998244353;
const int mod = 1e9+7;
#define int long long
int up(int a,int b) {return a<0?a/b:(a+b-1)/b;}
#define endl '\n'
#define all(x) (x).begin(),(x).end()
#define YES cout<<"YES"<<endl;
#define NO cout<<"NO"<<endl;
#define _ 0
#define db double
#define mk make_pair
#define pi acos(-1)
#define fi first
#define se second
#define INF 0x3f3f3f3f3f3f3f3f
#define PII pair<int,int>
#define fast ios::sync_with_stdio(false);cin.tie(nullptr);
int n,m,p[100010],fa[100010][17],d1[100010][17],d2[100010][17],depth[100010];
vector<PII>g[100010];
int find(int x){
if(x!=p[x])p[x]=find(p[x]);
return p[x];
}
void dfs(int x){
queue<int>q;q.push(x);
memset(depth,0x3f3f,sizeof depth);
depth[0]=0,depth[x]=1;
while(q.size()){
auto u=q.front();q.pop();
for(auto [v,w]:g[u]){
if(depth[v]>depth[u]+1){
depth[v]=depth[u]+1;
q.push(v);
fa[v][0]=u;
int dist1=w,dist2=-INF;
d1[v][0]=w,d2[v][0]=-INF;
for(int i=1;i<=16;i++){
int anc=fa[v][i-1];
fa[v][i]=fa[anc][i-1];
int d[4]={d1[v][i-1],d2[v][i-1],d1[anc][i-1],d2[anc][i-1]};
for(int j=0;j<4;j++){
if(dist1<d[j])dist2=dist1,dist1=d[j];
else if(dist1!=d[j]&&dist2<d[j])dist2=d[j];
}
d1[v][i]=dist1;
d2[v][i]=dist2;
}
}
}
}
}
int lca(int a,int b,int w){
static int d[200010];
int cnt=0;
if(depth[a]>depth[b])swap(a,b);
for(int i=16;i>=0;i--){
if(depth[fa[b][i]]>=depth[a]){
d[cnt++]=d1[b][i];
d[cnt++]=d2[b][i];
b=fa[b][i];
}
}
if(a!=b){
for(int i=16;i>=0;i--){
if(fa[a][i]!=fa[b][i]){
d[cnt++]=d1[a][i];
d[cnt++]=d2[a][i];
d[cnt++]=d1[b][i];
d[cnt++]=d2[b][i];
a=fa[a][i];
b=fa[b][i];
}
}
}
d[cnt++]=d1[a][0];
d[cnt++]=d2[a][0];
int dist1=-INF/2,dist2=-INF;
for(int i=0;i<cnt;i++){
if(d[i]>dist1)dist2=dist1,dist1=d[i];
else if(dist1!=d[i]&&d[i]>dist2)dist2=d[i];
}
if(w==dist1)return -dist2+w;
else return -dist1+w;
}
void solve(){
cin>>n>>m;
vector<tuple<int,int,int,bool>>v;
for(int i=1;i<=m;i++){
int a,b,c;cin>>a>>b>>c;
if(a!=b)v.push_back({c,a,b,0});
}
sort(all(v));
for(int i=1;i<=n;i++)p[i]=i;
int res=0;
for(int i=0;i<v.size();i++){
auto &[w,a,b,f]=v[i];
int pa=find(a),pb=find(b);
if(pa!=pb){
p[pa]=pb;
f=1;
res+=w;
}
}
for(int i=0;i<v.size();i++){
auto [w,a,b,f]=v[i];
if(f){
g[a].push_back({b,w});
g[b].push_back({a,w});
}
}
dfs(1);
int ans=INF;
for(int i=0;i<v.size();i++){
auto [w,a,b,f]=v[i];
if(!f)ans=min(ans,res+lca(a,b,w));
}
cout<<ans<<endl;
}
signed main() {
fast
int t=1;//cin>>t;
while(t--) {
solve();
}
return ~~(0^_^0);
}

Azusamitsusa
3个月前
//郑老师和阿梓一样可爱^_^
//r[i]表示我们需要的人数i时刻 num[i]表示i时刻我们有的人数 x[i]表示我们i时刻选择的人数
//0<=x[i]<=num[i]
//x[i-7]+x[i-6]+...+x[i]>=r[i]
//前缀和一下
//s[i]-s[i-8]>=r[i] 切记连边是左边去连右边
//要体现s[24]=s24 就必须要 s[24]>=c s[24]<=c 给0连起来就可以了
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#pragma GCC target("avx,sse2,sse3,sse4,mmx")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("inline")
#pragma GCC optimize("-fgcse")
#pragma GCC optimize("-fgcse-lm")
#pragma GCC optimize("-fipa-sra")
#pragma GCC optimize("-ftree-pre")
#pragma GCC optimize("-ftree-vrp")
#pragma GCC optimize("-fpeephole2")
#pragma GCC optimize("-ffast-math")
#pragma GCC optimize("-fsched-spec")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("-falign-jumps")
#pragma GCC optimize("-falign-loops")
#pragma GCC optimize("-falign-labels")
#pragma GCC optimize("-fdevirtualize")
#pragma GCC optimize("-fcaller-saves")
#pragma GCC optimize("-fcrossjumping")
#pragma GCC optimize("-funroll-loops")
#pragma GCC optimize("-fwhole-program")
#pragma GCC optimize("-freorder-blocks")
#pragma GCC optimize("-fschedule-insns")
#pragma GCC optimize("inline-functions")
#pragma GCC optimize("-ftree-tail-merge")
#pragma GCC optimize("-fschedule-insns2")
#pragma GCC optimize("-fstrict-aliasing")
#pragma GCC optimize("-fstrict-overflow")
#pragma GCC optimize("-falign-functions")
#pragma GCC optimize("-fcse-skip-blocks")
#pragma GCC optimize("-fcse-follow-jumps")
#pragma GCC optimize("-fsched-interblock")
#pragma GCC optimize("-fpartial-inlining")
#pragma GCC optimize("no-stack-protector")
#pragma GCC optimize("-freorder-functions")
#pragma GCC optimize("-findirect-inlining")
#pragma GCC optimize("-frerun-cse-after-loop")
#pragma GCC optimize("inline-small-functions")
#pragma GCC optimize("-finline-small-functions")
#pragma GCC optimize("-ftree-switch-conversion")
#pragma GCC optimize("-foptimize-sibling-calls")
#pragma GCC optimize("-fexpensive-optimizations")
#pragma GCC optimize("-funsafe-loop-optimizations")
#pragma GCC optimize("inline-functions-called-once")
#pragma GCC optimize("-fdelete-null-pointer-checks")
#include <bits/stdc++.h>
using namespace std;
const int N = 6e5 + 10;
//const int M = 998244353;
const int mod = 1e9+7;
#define int long long
#define db double
int up(int a,int b){return a<0?a/b:(a+b-1)/b;}
#define endl " \n"
#define all(x) (x).begin(),(x).end()
#define YES {cout<<"YES"<<endl;return;}
#define NO {cout<<"NO"<<endl;return;}
#define _ 0
#define pi acos(-1)
#define INF 0x3f3f3f3f3f3f3f3f
#define PII pair<int,int>
#define fast ios::sync_with_stdio(false);cin.tie(0);
int r[25],n,num[25],dist[25],cnt[25],st[25];
vector<PII>g[25];
bool spfa(int s24){
queue<int>q;
q.push(24);
memset(dist,-0x3f3f,sizeof dist);
memset(st,0,sizeof st);
memset(cnt,0,sizeof cnt);
dist[24]=s24;
while(q.size()){
auto u=q.front();q.pop();
if(st[u])continue;
st[u]=1;
for(auto [v,w]:g[u]){
if(dist[v]<dist[u]+w){
dist[v]=dist[u]+w;
cnt[v]=cnt[u]+1;
if(cnt[v]>=25)return true;
q.push(v);
st[v]=0;
}
}
}
return false;
}
void solve(){
for(int i=0;i<=24;i++){
st[i]=cnt[i]=num[i]=0;
}
for(int i=1;i<=24;i++)cin>>r[i];
cin>>n;
for(int i=1;i<=n;i++) {
int x;cin >> x;x++;
num[x]++;
}
for(int s24=0;s24<=1000;s24++){
for(int i=0;i<=24;i++){
g[i].clear();
}
for(int i=1;i<=24;i++){
g[i-1].push_back({i,0});
g[i].push_back({i-1,-num[i]});
if(i>=8)g[i-8].push_back({i,r[i]});
else g[i+16].push_back({i,r[i]-s24});
}
g[24].push_back({0,-s24});
g[0].push_back({24,s24});
if(!spfa(s24)){
cout<<s24<<endl;
return;
}
}
cout<<"No Solution"<<endl;
}
signed main(){
fast
int t;t=1;cin>>t;
while(t--) {
//run();
solve();
}
return ~~(0^_^0);
}

Azusamitsusa
3个月前
// max -> 最短路
// 奶牛排在队伍中的顺序和它们的编号是相同的。 x[i]<=x[i+1] i+1->i w=0
// x[b]-x[a]<=L x[b]<=x[a]+L a->b w=L
// x[b]-x[a]>=D x[a]<=x[b]-D b->a w=-D
//判-1就是check 负环 全部放进去跑一遍即可
//判-2就是看他跑完最短路之后dist[n]
#include<bits/stdc++.h>
using namespace std;
int n,m1,m2,dist[10010],st[10010],cnt[10010];
vector<pair<int,int>>g[10010];
bool spfa(int x){
queue<int>q;
memset(dist,0x3f,sizeof dist);
for(int i=1;i<=n;i++)cnt[i]=st[i]=0;
for(int i=1;i<=x;i++){
q.push(i);
dist[i]=0;
}
while(q.size()){
auto u=q.front();q.pop();
//cout<<dist[u]<<' '<<u<<endl;
if(st[u])continue;
st[u]=1;
for(auto [v,w]:g[u]){
if(dist[v]>dist[u]+w){
dist[v]=dist[u]+w;
cnt[v]=cnt[u]+1;
if(cnt[v]>=n)return true;
q.push(v);
st[v]=0;
}
}
}
return false;
}
int main(){
cin>>n>>m1>>m2;
for(int i=1;i<n;i++){
g[i+1].push_back({i,0});
}
while(m1--){
int a,b,w;cin>>a>>b>>w;
g[a].push_back({b,w});
}
while(m2--){
int a,b,w;cin>>a>>b>>w;
g[b].push_back({a,-w});
}
if(spfa(n)){
cout<<-1<<endl;
return 0;
}
spfa(1);
if(dist[n]!=0x3f3f3f3f)cout<<dist[n]<<endl;
else cout<<-2<<endl;
return 0;
}

Azusamitsusa
3个月前

#### C++ 代码

//郑老师和阿梓一样可爱^_^

#include <bits/stdc++.h>
using namespace std;
int n,idx,son[3000010][2],a[100010],dp[3000010];
int p=0;
for(int i=30;i>=0;i--){
int u=x>>i&1;
if(!son[p][u])son[p][u]=++idx;
p=son[p][u];
}
}
void dfs(int p,int now){
int l=son[p][0],r=son[p][1];
if(l)dfs(l,now-1);
if(r)dfs(r,now-1);
if(l&&!r)dp[p]+=dp[l];
else if(r&&!l)dp[p]+=dp[r];
else if(r&&l)dp[p]=min(dp[l],dp[r])+(1<<now);
}
signed main(){
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i];
}
dfs(0,30);
cout<<dp[0]<<endl;
return 0;
}

Azusamitsusa
3个月前
//郑老师和阿梓一样可爱^_^
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#pragma GCC target("avx,sse2,sse3,sse4,mmx")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("inline")
#pragma GCC optimize("-fgcse")
#pragma GCC optimize("-fgcse-lm")
#pragma GCC optimize("-fipa-sra")
#pragma GCC optimize("-ftree-pre")
#pragma GCC optimize("-ftree-vrp")
#pragma GCC optimize("-fpeephole2")
#pragma GCC optimize("-ffast-math")
#pragma GCC optimize("-fsched-spec")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("-falign-jumps")
#pragma GCC optimize("-falign-loops")
#pragma GCC optimize("-falign-labels")
#pragma GCC optimize("-fdevirtualize")
#pragma GCC optimize("-fcaller-saves")
#pragma GCC optimize("-fcrossjumping")
#pragma GCC optimize("-funroll-loops")
#pragma GCC optimize("-fwhole-program")
#pragma GCC optimize("-freorder-blocks")
#pragma GCC optimize("-fschedule-insns")
#pragma GCC optimize("inline-functions")
#pragma GCC optimize("-ftree-tail-merge")
#pragma GCC optimize("-fschedule-insns2")
#pragma GCC optimize("-fstrict-aliasing")
#pragma GCC optimize("-fstrict-overflow")
#pragma GCC optimize("-falign-functions")
#pragma GCC optimize("-fcse-skip-blocks")
#pragma GCC optimize("-fcse-follow-jumps")
#pragma GCC optimize("-fsched-interblock")
#pragma GCC optimize("-fpartial-inlining")
#pragma GCC optimize("no-stack-protector")
#pragma GCC optimize("-freorder-functions")
#pragma GCC optimize("-findirect-inlining")
#pragma GCC optimize("-frerun-cse-after-loop")
#pragma GCC optimize("inline-small-functions")
#pragma GCC optimize("-finline-small-functions")
#pragma GCC optimize("-ftree-switch-conversion")
#pragma GCC optimize("-foptimize-sibling-calls")
#pragma GCC optimize("-fexpensive-optimizations")
#pragma GCC optimize("-funsafe-loop-optimizations")
#pragma GCC optimize("inline-functions-called-once")
#pragma GCC optimize("-fdelete-null-pointer-checks")
#include <bits/stdc++.h>
using namespace std;
const int N = 6e5 + 10;
//const int M = 998244353;
const int mod = 1e9+7;
#define int long long
#define db double
int up(int a,int b){return a<0?a/b:(a+b-1)/b;}
#define endl " \n"
#define all(x) (x).begin(),(x).end()
#define YES {cout<<"YES"<<endl;return;}
#define NO {cout<<"NO"<<endl;return;}
#define _ 0
#define pi acos(-1)
#define INF 0x3f3f3f3f3f3f3f3f
#define PII pair<int,int>
#define fast ios::sync_with_stdio(false);cin.tie(0);
int n,dist[500010];
vector<PII>g[500010];
bool st[500010];
void spfa(){
queue<int>q;
q.push(0);
memset(dist,-0x3f3f,sizeof dist);
dist[0]=0;
while(q.size()){
auto u=q.front();q.pop();
if(st[u])continue;
st[u]=true;
for(auto [v,w]:g[u]){
if(dist[v]<dist[u]+w){
dist[v]=dist[u]+w;
q.push(v);
st[v]=false;
}
}
}
}
void solve(){
cin>>n;
for(int i=1;i<=n;i++){
int a,b,w;cin>>a>>b>>w;
a++,b++;
g[a-1].push_back({b,w});
}
for(int i=1;i<500010;i++){
g[i-1].push_back({i,0});
g[i].push_back({i-1,-1});
}
spfa();
cout<<dist[500001]<<endl;
}
signed main(){
fast
int t;t=1;//cin>>t;
while(t--) {
//run();
solve();
}
return ~~(0^_^0);
}

Azusamitsusa
3个月前
//郑老师和阿梓一样可爱^_^
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#pragma GCC target("avx,sse2,sse3,sse4,mmx")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("inline")
#pragma GCC optimize("-fgcse")
#pragma GCC optimize("-fgcse-lm")
#pragma GCC optimize("-fipa-sra")
#pragma GCC optimize("-ftree-pre")
#pragma GCC optimize("-ftree-vrp")
#pragma GCC optimize("-fpeephole2")
#pragma GCC optimize("-ffast-math")
#pragma GCC optimize("-fsched-spec")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("-falign-jumps")
#pragma GCC optimize("-falign-loops")
#pragma GCC optimize("-falign-labels")
#pragma GCC optimize("-fdevirtualize")
#pragma GCC optimize("-fcaller-saves")
#pragma GCC optimize("-fcrossjumping")
#pragma GCC optimize("-funroll-loops")
#pragma GCC optimize("-fwhole-program")
#pragma GCC optimize("-freorder-blocks")
#pragma GCC optimize("-fschedule-insns")
#pragma GCC optimize("inline-functions")
#pragma GCC optimize("-ftree-tail-merge")
#pragma GCC optimize("-fschedule-insns2")
#pragma GCC optimize("-fstrict-aliasing")
#pragma GCC optimize("-fstrict-overflow")
#pragma GCC optimize("-falign-functions")
#pragma GCC optimize("-fcse-skip-blocks")
#pragma GCC optimize("-fcse-follow-jumps")
#pragma GCC optimize("-fsched-interblock")
#pragma GCC optimize("-fpartial-inlining")
#pragma GCC optimize("no-stack-protector")
#pragma GCC optimize("-freorder-functions")
#pragma GCC optimize("-findirect-inlining")
#pragma GCC optimize("-frerun-cse-after-loop")
#pragma GCC optimize("inline-small-functions")
#pragma GCC optimize("-finline-small-functions")
#pragma GCC optimize("-ftree-switch-conversion")
#pragma GCC optimize("-foptimize-sibling-calls")
#pragma GCC optimize("-fexpensive-optimizations")
#pragma GCC optimize("-funsafe-loop-optimizations")
#pragma GCC optimize("inline-functions-called-once")
#pragma GCC optimize("-fdelete-null-pointer-checks")
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
//const int M = 998244353;
const int mod = 1e9+7;
//#define int long long
#define db double
int up(int a,int b){return a<0?a/b:(a+b-1)/b;}
#define endl " \n"
#define all(x) (x).begin(),(x).end()
#define YES {cout<<"YES"<<endl;return;}
#define NO {cout<<"NO"<<endl;return;}
#define _ 0
#define pi acos(-1)
#define INF 0x3f3f3f3f3f3f3f3f
#define PII pair<int,int>
#define fast ios::sync_with_stdio(false);cin.tie(0);
int n,m,cnt[100010],q[100010],h[N],e[3*N],w[3*N],ne[3*N], idx;
long long dist[100010];
bool st[100010];
void add(int a, int b, int c){
e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++;
}
bool spfa(){
int hh = 0, tt = 1;
q[0]=0;
memset(dist,-0x3f,sizeof dist);
dist[0]=0;
st[0]=true;
while(hh!=tt){
auto t=q[--tt];
st[t]=false;
for (int i = h[t]; ~i; i = ne[i])
{
int j = e[i];
if (dist[j] < dist[t] + w[i])
{
dist[j] = dist[t] + w[i];
cnt[j] = cnt[t] + 1;
if (cnt[j] >= n + 1) return true;
if (!st[j])
{
q[tt ++ ] = j;
st[j] = true;
}
}
}
}
return false;
}
void solve(){
cin>>n>>m;
memset(h, -1, sizeof h);
for(int i=1;i<=m;i++){
int x,a,b;cin>>x>>a>>b;
else if (x == 2) add(a, b, 1);
else if (x == 3) add(b, a, 0);
else if (x == 4) add(b, a, 1);
}
if(spfa())cout<<-1<<endl;
else{
long long ans=0;
for(int i=1;i<=n;i++){
ans+=dist[i];
}
cout<<ans<<endl;
}
}
signed main(){
fast
int t;t=1;//cin>>t;
while(t--) {
//run();
solve();
}
return ~~(0^_^0);
}

Azusamitsusa
3个月前
//这里填你的代码^^
//注意代码要放在两组三个点之间，才可以正确显示代码高亮哦~
//优化：优化点数 只看两个字符最多就是26*26个点
//时间复杂度大概是1e8但是过不了呢
//郑老师和阿梓一样可爱^_^

#include <bits/stdc++.h>
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#pragma GCC target("avx,sse2,sse3,sse4,mmx")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("inline")
#pragma GCC optimize("-fgcse")
#pragma GCC optimize("-fgcse-lm")
#pragma GCC optimize("-fipa-sra")
#pragma GCC optimize("-ftree-pre")
#pragma GCC optimize("-ftree-vrp")
#pragma GCC optimize("-fpeephole2")
#pragma GCC optimize("-ffast-math")
#pragma GCC optimize("-fsched-spec")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("-falign-jumps")
#pragma GCC optimize("-falign-loops")
#pragma GCC optimize("-falign-labels")
#pragma GCC optimize("-fdevirtualize")
#pragma GCC optimize("-fcaller-saves")
#pragma GCC optimize("-fcrossjumping")
#pragma GCC optimize("-funroll-loops")
#pragma GCC optimize("-fwhole-program")
#pragma GCC optimize("-freorder-blocks")
#pragma GCC optimize("-fschedule-insns")
#pragma GCC optimize("inline-functions")
#pragma GCC optimize("-ftree-tail-merge")
#pragma GCC optimize("-fschedule-insns2")
#pragma GCC optimize("-fstrict-aliasing")
#pragma GCC optimize("-fstrict-overflow")
#pragma GCC optimize("-falign-functions")
#pragma GCC optimize("-fcse-skip-blocks")
#pragma GCC optimize("-fcse-follow-jumps")
#pragma GCC optimize("-fsched-interblock")
#pragma GCC optimize("-fpartial-inlining")
#pragma GCC optimize("no-stack-protector")
#pragma GCC optimize("-freorder-functions")
#pragma GCC optimize("-findirect-inlining")
#pragma GCC optimize("-frerun-cse-after-loop")
#pragma GCC optimize("inline-small-functions")
#pragma GCC optimize("-finline-small-functions")
#pragma GCC optimize("-ftree-switch-conversion")
#pragma GCC optimize("-foptimize-sibling-calls")
#pragma GCC optimize("-fexpensive-optimizations")
#pragma GCC optimize("-funsafe-loop-optimizations")
#pragma GCC optimize("inline-functions-called-once")
#pragma GCC optimize("-fdelete-null-pointer-checks")

using namespace std;
const int mod = 998244353;
const int N = 5e5 + 10;
//const int M = 998244353;
//#define int long long
#define db double
int up(int a,int b){return a<0?a/b:(a+b-1)/b;}
#define endl " \n"
#define all(x) (x).begin(),(x).end()
#define YES {cout<<"YES"<<endl;return;}
#define NO {cout<<"NO"<<endl;return;}
#define _ 0
#define pi acos(-1)
#define INF 0x3f3f3f3f3f3f3f3f
#define PII pair<int,int>
#define fast ios::sync_with_stdio(false);cin.tie(0);
int n;
vector<pair<int,db>>g[1010];
bool check(db mid){ //676*10000*log
queue<int>q;
for(int i=0;i<=676;i++)if(g[i].size())q.push(i);
vector<int>cnt(1010),st(1010);
vector<db>dist(1010);
int count=0;
while(q.size()){
auto u=q.front();q.pop();
if(st[u])continue;
st[u]=1;
for(auto [v,W]:g[u]){
db c=mid-W;
if(dist[v]>dist[u]+c){
dist[v]=dist[u]+c;
cnt[v]=cnt[u]+1;
if(++count>=10000)return true;
if(cnt[v]>=676){
//cout<<"true:"<<mid<<endl;
return true;
}
q.push(v);
st[v]=0;
}
}
}
//cout<<"false:"<<mid<<endl;
return false;
}
void solve(){
while(cin>>n,n){
for(int i=0;i<=676;i++){
g[i].clear();
}
for(int i=1;i<=n;i++){
string s;cin>>s;
if(s.size()<2)continue;
int v=(s[0]-'a')*26+(s[1]-'a'),u=(s[s.size()-2]-'a')*26+s.back()-'a';
//cout<<u<<' '<<v<<' '<<s.size()<<endl;
g[u].push_back({v,s.size()});
}
db l=0,r=1000;
if(!check(0)){
cout<<"No solution"<<endl;
continue;
}
while(r-l>=1e-4){
db mid=(l+r)/2;
if(check(mid))l=mid;
else r=mid;
}
printf("%.2f\n",l);
}
}
signed main(){
fast
int t;t=1;//cin>>t;
while(t--) {
//run();
solve();
}
return ~~(0^_^0);
}

Azusamitsusa
3个月前
//郑老师和阿梓一样可爱^_^

#include <bits/stdc++.h>
using namespace std;
const int N = 6e5 + 10;
//const int M = 998244353;
const int mod = 1e9+7;
#define int long long
#define db double
int up(int a,int b){return a<0?a/b:(a+b-1)/b;}
#define endl " \n"
#define all(x) (x).begin(),(x).end()
#define YES {cout<<"YES"<<endl;return;}
#define NO {cout<<"NO"<<endl;return;}
#define _ 0
#define pi acos(-1)
#define INF 0x3f3f3f3f3f3f3f3f
#define PII pair<int,int>
#define fast ios::sync_with_stdio(false);cin.tie(0);
int n,m;
db w[1010];
vector<pair<int,db>>G[1010];
bool check(db mid){
vector<pair<int,db>>g[n+1];
for(int u=1;u<=n;u++){
for(auto [v,W]:G[u]){
db c=mid*(db)W-(db)w[u];
g[u].push_back({v,c});
}
}
queue<int>q;
vector<int>st(n+1),cnt(n+1);
vector<db>dist(n+1);
for(int i=1;i<=n;i++)q.push(i);
while(q.size()){
auto u=q.front();q.pop();
if(st[u])continue;
st[u]=1;
for(auto [v,W]:g[u]){
if(dist[v]>dist[u]+W){
cnt[v]=cnt[u]+1;
if(cnt[v]>=n)return true;
dist[v]=dist[u]+W;
q.push(v);
st[v]=0;
}
}
}
return false;
}
void solve(){
cin>>n>>m;
for(int i=1;i<=n;i++)cin>>w[i];
for(int i=1;i<=m;i++){
int a,b,c;cin>>a>>b>>c;
G[a].push_back({b,c});
}
db l=0,r=1000;
while(r-l>=1e-4){
db mid=(l+r)/2;
if(check(mid))l=mid;
else r=mid;
}
printf("%.2lf",l);
}
signed main(){
fast
int t;t=1;//cin>>t;
while(t--) {
//run();
solve();
}
return ~~(0^_^0);
}

Azusamitsusa
3个月前
#include <bits/stdc++.h>
using namespace std;

void solve(){
int n,m1,m2;cin>>n>>m1>>m2;
vector<pair<int,int>>g[n+1];
while(m1--){
int a,b,w;cin>>a>>b>>w;
g[a].push_back({b,w});
g[b].push_back({a,w});
}
while(m2--){
int a,b,w;cin>>a>>b>>w;
g[a].push_back({b,-w});
}
queue<int>q;
vector<int>dist(n+1),st(n+1),cnt(n+1);
for(int i=1;i<=n;i++)q.push(i);
while(q.size()){
auto u=q.front();q.pop();
if(st[u])continue;
st[u]=1;
for(auto [v,w]:g[u]){
if(dist[v]>dist[u]+w){
dist[v]=dist[u]+w;
cnt[v]=cnt[u]+1;
if(cnt[v]>=n){
cout<<"YES"<<endl;
return;
}
q.push(v);
st[v]=0;
}
}
}
cout<<"NO"<<endl;
}
int main(){
int t;cin>>t;
while(t--){
solve();
}
return 0;
}