求调几道题，每题悬赏1关注
- 板块学术版
- 楼主Mortidesperatslav
- 当前回复2
- 已保存回复2
- 发布时间2024/3/3 21:56
- 上次更新2024/3/4 13:47:51
查看原帖
被骇客银狼阻止的越权访问保存失败
求调几道题，每题悬赏1关注
悬赏1关注或者在天波服要2钻石
CF487E
#include<bits/stdc++.h>
using namespace std;
int ig[114514], dfn[114514], low[114514], col[114514], vl[114514];
int n, m, a1, a2, cnt, ign, ans, ccnt, qq;
bool vis[114514];
vector<int> G[114514], BCC[114514], CST[114514];
stack<int> s;
queue<int> q;
bool vvis[114514], op[114514];
void tarjan(int u){
dfn[u] = low[u] = ++cnt;
int sn = 0;
s.push(u);
for (auto &v : G[u]){
if (!dfn[v]){
sn++;
tarjan(v);
low[u] = min(low[u], low[v]);
if (low[v] >= dfn[u]){
ccnt++;
while (!s.empty()){
int vv = s.top();
s.pop();
CST[n + ccnt].push_back(vv);
CST[vv].push_back(n + ccnt);
// cerr << vv << "<->" << n + ccnt << "\n";
if (v == vv)
break;
}
CST[n + ccnt].push_back(u);
CST[u].push_back(n + ccnt);
// cerr << u << "<->" << n + ccnt << "\n";
}
}else
low[u] = min(low[u], dfn[v]);
}
}
long long a[100005];
int fa[100005],hs[100005],sz[100005],top[100005],ddfn[100005],rdfn[100005],dep[100005];
int vst;
void dfs(int u,int fat) {
fa[u]=fat;
sz[u]=1;
dep[u]=dep[fat]+1;
for(auto &v:CST[u]) {
if(v==fat)continue;
dfs(v,u);
sz[u]+=sz[v];
if(sz[v]>sz[hs[u]])hs[u]=v;
}
}
void cut(int u,int tp) {
ddfn[u]=++vst;
rdfn[vst]=u;
top[u]=tp;
if(hs[u]) {
cut(hs[u],tp);
for(auto &v:G[u])if(v!=fa[u]&&v!=hs[u])cut(v,v);
}
}
long long tr[800020],trr[800020];
void pup(int u) {
tr[u]=tr[u<<1]+tr[u<<1|1];
trr[u]=min(trr[u<<1],trr[u<<1|1]);
}
void build(int u,int le,int ri) {
if(le==ri) {
tr[u]=trr[u]=a[rdfn[le]];
return;
}
int mid=(le+ri)>>1;
build(u<<1,le,mid);
build(u<<1|1,mid+1,ri);
pup(u);
}
bool inr(int le,int ri,int L,int R) {
return (L<=le)&&(ri<=R);
}
bool otr(int le,int ri,int L,int R) {
return (le>R)||(ri<L);
}
long long query(int u,int le,int ri,int L,int R) {
// cout << trr[u] << "\n";
if(inr(le,ri,L,R))return trr[u];
else if(!otr(le,ri,L,R)) {
int mid=(le+ri)>>1;
return min(query(u<<1,le,mid,L,R),query(u<<1|1,mid+1,ri,L,R));
}
return INT_MAX;
}
long long qry(int x,int y) {
long long ans=INT_MAX;
while(top[x]!=top[y]) {
if(dep[top[x]]<dep[top[y]])swap(x,y);
ans=min(ans,query(1,1,n+ccnt,ddfn[top[x]],ddfn[x]));
x=fa[top[x]];
}
return min(ans,query(1,1,n+ccnt,min(ddfn[x],ddfn[y]),max(ddfn[x],ddfn[y])));
}
void update(int u,int le,int ri,int ft,long long x) {
int mid=(le+ri)>>1;
if(le==ri){
tr[u]=trr[u]=x;
return;
}
if(ft<=mid)update(u<<1,le,mid,ft,x);
else update(u<<1|1,mid+1,ri,ft,x);
pup(u);
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
cin >> n >> m >> qq;
for(int i=1; i<=n; i++)cin>>a[i];
for (int i = 1; i <= m; i++){
int u, v;
cin >> u >> v;
G[u].push_back(v);
G[v].push_back(u);
}
for (int i = 1; i <= n; i++)
if (!dfn[i]){
tarjan(i);
s.pop();
}
for (int i = n + 1; i <= n + ccnt; i++)
a[i] = INT_MAX;
int r = 1;
for(int i=1;i<=n+ccnt;i++)sort(CST[i].begin(),CST[i].end(),[](int x,int y){return a[x]<a[y];});
dfs(r,0);
cut(r,0);
build(1,1,n+ccnt);
while(qq--) {
string ord;
cin>>ord;
if(ord=="C"){
int u,v;
cin>>u>>v;
update(1,1,n+ccnt,ddfn[u],v);
}else if(ord=="A"){
int u,v;
cin>>u>>v;
cout<<qry(u,v)<<'\n';
}
}
}
P4645
#include<bits/stdc++.h>
using namespace std;
int ig[114514], dfn[114514], low[114514], col[114514], vl[114514];
int n, m, a1, a2, cnt, ign, ans;
bool vis[114514];
vector<int> G[114514], NG[114514];
stack<int> s;
queue<int> q;
long long dis[114514];
int in[114514];
void tarjan(int u){
dfn[u] = low[u] = ++cnt;
s.push(u);
vis[u] = 1;
for (auto &v : G[u]){
if (!dfn[v]){
tarjan(v);
low[u] = min(low[u], low[v]);
}else if (vis[v])
low[u] = min(low[u], dfn[v]);
}
if (dfn[u] == low[u]){
while (!s.empty()){
int v = s.top();
s.pop();
vis[v] = 0;
col[v] = u;
vl[u]++;
if (u == v)
break;
}
}
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
cin >> n >> m;
for (int i = 1; i <= m; i++){
int u, v;
cin >> u >> v;
G[u].push_back(v);
}
for (int i = 1; i <= n; i++)
if (!dfn[i])
tarjan(i);
for (int i = 1; i <= n; i++)
for (auto v : G[i]){
if (col[i] == col[v])
continue;
NG[col[i]].push_back(col[v]);
ig[col[i]] = ig[col[v]] = 1;
in[col[v]]++;
// cout << col[i] << "->" << col[v] << "\n";
}
for (int i = 1; i <= n; i++)
if (col[i] == i && !ig[i])
ig[i] = 1;
for (int i = 1; i <= n; i++)
if (ig[i])
ign++;
if (vl[1] != 1 || col[1] != 1){
cout << "inf";
return 0;
}
q.push(1);
dis[1] = 1;
while (!q.empty()){
int u = q.front();
q.pop();
// cout << u << "\n";
for (auto v : NG[u]){
in[v]--;
if (!in[v])
q.push(v);
// cout << v << " " << in[v] << "\n";
if (dis[v] == -1)
continue;
if (dis[u] == -1 || vl[v] > 1){
dis[v] = -1;
// cout << u << " " << dis[u] << " " << v << " " << dis[v] << "\n";
continue;
}
dis[v] = (dis[v] + dis[u]) % 1000000000;
//cout << u << " " << dis[u] << " " << v << " " << dis[v] << "\n";
}
}
if (dis[col[2]] == -1)
cout << "inf";
else
cout << dis[col[2]];
}
P3244
#include<bits/stdc++.h>
#define it int
#define ti int
#define fr for
#define rf for
#define pb push_back
#define ll long long
using namespace std;
it n, m, x, y;
vector<int> G[114514];
it inn[114514], in[114514];
queue<int> q;
ll rs = 1, rss = 1;
ll qpow(ll x, it k){
ll ans = 1;
while(k){
if (k & 1)
ans = (ans * x) % 1000000007;
x = (x * x) % 1000000007;
k >>= 1;
}
return ans;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
cin >> n >> m >> x >> y;
for (it i = 1; i <= m; i++){
it u, v;
cin >> u >> v;
G[u].pb(v);
in[v]++;
inn[v]++;
}
G[x].pb(y);
in[y]++;
inn[y]++;
for (it i = 2; i <= n; i++)
rs = (rs * in[i]) % 1000000007;
for (it i = 1; i <= n; i++)
if (!in[i])
q.push(i);
while(!q.empty()){
int u = q.front();
q.pop();
for (auto v : G[u]){
in[v]--;
if (!in[v])
q.push(v);
}
}
rss = rs;
for (it i = 2; i <= n; i++)
if (in[i])
rss = (rss * qpow(inn[i], 1000000005)) % 1000000007;
cout << ((rs - rss) % 1000000007 + 1000000007) % 1000000007;
}
P6381
#include<bits/stdc++.h>
using namespace std;
int n, m, k, cnt, ans;
int in[214514], srt[214514];
struct node
{
public:
int v, w, l, nx;
bool operator <(node b)const
{
return this->v < b.v;
}
};
node G[114514<<1];
queue<int>q;
int a[214514], ccnt, pos[214514];
bool vis[214514];
int h[214514];
int ec;
void addedge(int u, int v, int w, int l)
{
G[++ec].v = v;
G[ec].w = w;
G[ec].l = l;
G[ec].nx = h[u];
h[u] = ec;
}
void sieve(int n)
{
for(int i = 2; i <= n; i++)
{
if(!vis[i])
{
a[++ccnt] = i;
pos[i] = ccnt;
}
for(int j = 1; j <= ccnt; j++)
{
if(i * a[j] > n)
break;
vis[i * a[j]] = 1;
pos[i * a[j]] = j;
if(i % a[j] == 0)
break;
}
}
}
const int mod[] = {1145141, 19260818 - 1};
int d[114514<<1], dd[114514<<1];
int dc;
int hsh(int x){
long long res = 0;
for(int i = 0; i < dc; i++)
if(dd[i])
res = (res + d[i] ^ 11451419ll + dd[i] ^ 114514ll) % mod[x];
return res;
}
int hs[114514<<1][2], p[114514<<1][2];
void init(){
for(int i = 1; i <= m; i++)
{
memset(d, 0, sizeof d);
memset(dd, 0, sizeof dd);
dc=0;
for(int e = G[i].w, pr = 0; e != 1; e /= a[pos[e]]){
if(pr == pos[e])
{
if(++dd[dc - 1] == k)
dd[dc - 1] = 0;
else{
d[++dc] = pos[e];
dd[dc] = (k != 1);
pr = pos[e];
}
}
}
hs[i][0] = hsh(0);
hs[i][1] = hsh(1);
for (int j = 0; j < dc; j++)
if (dd[j])
dd[j] = k - dd[j];
p[i][0] = hsh(0);
p[i][1] = hsh(1);
}
}
struct noode{
public:
int h,hh;
};
map<node,int>f[114514<<1];
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
cin >> n >> m >> k;
for(int i = 1; i <= m; i++)
{
int u, v, w, l;
cin >> u >> v >> w >> l;
addedge(u, v, w, l);
in[v]++;
}
sieve(100000);
for(int i = 1; i <= m; i++)
if(!in[i])
q.push(i);
while(!q.empty())
{
int u = q.front();
q.pop();
srt[++cnt] = u;
for(int e = h[u]; e; e = G[e].nx)
{
int v = G[e].v;
in[v]--;
if(!in[v])
q.push(v);
}
}
init();
node k, j;
for(int i = n; i; i--)
{
int u = srt[i];
for(int e = h[u]; e; e = G[e].nx){
int v = G[e].v;
k = {hs[e][0], hs[e][1]};
f[u][k] = max(f[u][k], G[e].l);
j = {p[e][0], p[e][1]};
f[u][k] = max(f[u][k], G[e].l + f[v][j]);
ans = max(ans, f[u][k]);
}
}
cout << ans << "\n";
}
加载中...