QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#864827#4809. Maximum Rangelsj2009WA 0ms12104kbC++146.7kb2025-01-21 09:40:282025-01-21 09:40:28

Judging History

你现在查看的是最新测评结果

  • [2025-01-21 09:40:28]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:12104kb
  • [2025-01-21 09:40:28]
  • 提交

answer

#include<bits/stdc++.h>
// #define int long long
// #pragma GCC optimize(3,"Ofast","inline")
#define debug(...) fprintf(stderr,__VA_ARGS__)
#define ll long long
#define bint __int128
#define ull unsigned long long
#define uint unsigned int
#define ld double
#define PII pair<int,int>
#define chkmax(a,b) a=max(a,b)
#define chkmin(a,b) a=min(a,b)
#define rep(k,l,r) for(int k=l;k<=r;++k)
#define per(k,r,l) for(int k=r;k>=l;--k)
#define cl(f,x) memset(f,x,sizeof(f))
#define pcnt(x) __builtin_popcount(x)
#define lg(x) (31-__builtin_clz(x))
using namespace std;
void file_IO() {
    freopen("test.in","r",stdin);
    freopen("test.out","w",stdout);
}
bool M1;
const int INF=0x3f3f3f3f;
const ll INFLL=0x3f3f3f3f3f3f3f3f;
const ld eps=1e-9;
struct Flow {
	static const int N=1e5+5,M=1e6+5;
	int head[N],cur[N],len=1;
	struct node {
		int from,to,nxt,cap,flow;
	}; node edge[M<<1];
	map<PII,int> belong;
	void init() {
		cl(head,0); len=1;
		belong.clear();
	}
	void print(int u,int v,int w) {
		if(w==INF)
			debug("%d %d inf\n",u,v);
		else
			debug("%d %d %d\n",u,v,w);
	}
	void print_edge() {
		for(auto x:belong) {
			int u=x.first.first,v=x.first.second,w=edge[x.second].cap;
			print(u,v,w);
		}
	}
	void add_edge(int u,int v,int w) {
		int &x1=belong[make_pair(u,v)],&x2=belong[make_pair(v,u)];
		edge[++len]={u,v,head[u],w,0}; head[u]=len;
		x1=len;
		edge[++len]={v,u,head[v],w,0}; head[v]=len;
		x2=len;
	}
	int flow(int u,int v) {
		int x=belong[make_pair(u,v)];
		return edge[x].flow;
	}
	bool is_cut(int u,int v) {
		int x=belong[make_pair(u,v)];
		return edge[x].cap==edge[x].flow;
	}
	int d[N]; 
	bool used[N];
	bool bfs(int s,int t,int n) {
		rep(i,0,n) {
			used[i]=false;
			d[i]=0;
		}
		queue<int> q;
		q.push(s); used[s]=true;
		while(!q.empty()) {
			int u=q.front(); q.pop();
			if(u==t)
				return true;
			for(int i=head[u];i;i=edge[i].nxt) {
				int v=edge[i].to,cap=edge[i].cap,flow=edge[i].flow;
				if(!used[v]&&cap>flow) {
					used[v]=true; 
					d[v]=d[u]+1; 
					q.push(v);
				}
			}
		}
		return false;
	}
	int dfs(int u,int flow,int t) {
		if(u==t||!flow)
			return flow;
		int ret=0;
		for(int &i=cur[u];i;i=edge[i].nxt) {
			int v=edge[i].to; 
			if((d[v]==d[u]+1)&&edge[i].cap>edge[i].flow) {
				int delta=dfs(v,min(flow-ret,edge[i].cap-edge[i].flow),t);
				ret+=delta;
				edge[i].flow+=delta;
				edge[i^1].flow-=delta;
				if(ret==flow)
					return ret;
			}
		}
		return ret;
	}
	int dinic(int s,int t,int n) {
		int res=0;
		while(bfs(s,t,n)) {
			rep(i,0,n)
			cur[i]=head[i];
			res+=dfs(s,INF,t);
		}
		return res;
	}
	void reset() {
		rep(i,2,len)
		edge[i].flow=0;
	}
	void reset(int u,int v,int s,int t,int n) {
		dinic(u,s,n);
		dinic(t,v,n);
		int x=belong[make_pair(u,v)];
		edge[x].cap=edge[x].flow=edge[x^1].cap=edge[x^1].flow=0;
	}
	void del(int u,int v) {
		int x=belong[make_pair(u,v)];
		edge[x].cap=edge[x].flow=edge[x^1].cap=edge[x^1].flow=0;
	}
	bool vis[N];
	void get(int u,int n,vector<int> &vec) {
		rep(i,0,n)
		vis[i]=false;
		vec.clear();
		queue<int> q;
		q.push(u);
		vis[u]=true;
		while(!q.empty()) {
			int u=q.front(); q.pop();
			vec.push_back(u);
			for(int i=head[u];i;i=edge[i].nxt) {
				int v=edge[i].to,cap=edge[i].cap,flow=edge[i].flow;
				if(!vis[v]&&cap!=flow) {
					q.push(v);
					vis[v]=true;
				}
			}
		}
	}
}; Flow g;
const int N=1e5+5;
int head[N],len;
struct node {
    int to,w,nxt;
}; node edge[N<<1];
void add_edge(int u,int v,int w) {
    edge[++len]={v,w,head[u]}; head[u]=len;
}
int dfn[N],low[N],p;
bool bridge[N];
void tarjan(int u,int from) {
    dfn[u]=low[u]=++p;
    for(int i=head[u];i;i=edge[i].nxt) {
        int v=edge[i].to,w=edge[i].w;
        if(!dfn[v]) {
            tarjan(v,w);
            chkmin(low[u],low[v]);
            if(low[v]==dfn[v])
                bridge[w]=true,debug("bridge %d\n",w);
        } else if(from!=w)
            chkmin(low[u],dfn[v]);
    }
}
vector<int> vec[N];
bool used[N];
int c;
void dfs(int u) {
    used[u]=true;
    for(int i=head[u];i;i=edge[i].nxt) {
        int v=edge[i].to,w=edge[i].w;
        if(!bridge[w]) {
            vec[c].push_back(w);
            if(!used[v])
                dfs(v);
        }
    }
}
int a[N],b[N],d[N],mne[N],mxe[N];
bool usededge[N],visedge[N];
vector<int> tmp;
void dfs1(int u) {
    tmp.push_back(u);
	int cnt=0;
    for(int i=head[u];i;i=edge[i].nxt) {
        int v=edge[i].to,w=edge[i].w;
        if(usededge[w]) {
			++cnt;
            if(!visedge[w]) {
				visedge[w]=true;
				dfs1(v);
			}
        }
    }
	assert((cnt+1)&1);
}
void solve() {
    int n,m;
    scanf("%d%d",&n,&m);
    rep(i,1,m) {
        scanf("%d%d%d",&a[i],&b[i],&d[i]);
        add_edge(a[i],b[i],i);
        add_edge(b[i],a[i],i);
    }
    rep(i,1,n) {
        if(!dfn[i])
            tarjan(i,0);
    }
    int mx=-INF;
    rep(i,1,n) {
        if(!used[i]) {
            ++c;
            dfs(i);
            sort(vec[c].begin(),vec[c].end());
            vec[c].erase(unique(vec[c].begin(),vec[c].end()),vec[c].end());
            if(vec[c].empty())
                continue;
            for(auto x:vec[c]) {
                if(!mne[c]||d[x]<d[mne[c]])
                    mne[c]=x;
                if(!mxe[c]||d[x]>=d[mxe[c]])
                    mxe[c]=x;
            }
            chkmax(mx,d[mxe[c]]-d[mne[c]]);
        }
    }
    printf("%d\n",mx);
    rep(i,1,c) {
        if(mne[i]&&d[mxe[i]]-d[mne[i]]==mx) {
            // debug("ok\n");
            for(auto x:vec[i]) {
                if(x!=mxe[i]&&x!=mne[i])
                    g.add_edge(a[x],b[x],1);
            }
            int s=0,t=n+1;
            g.add_edge(s,a[mne[i]],1);
            g.add_edge(s,b[mne[i]],1);
            g.add_edge(a[mxe[i]],t,1);
            g.add_edge(b[mxe[i]],t,1);
            g.dinic(s,t,t);
            // g.print_edge();
            usededge[mne[i]]=usededge[mxe[i]]=true;
            for(auto x:vec[i]) {
                if(x!=mxe[i]&&x!=mne[i]) {
                    if(g.flow(a[x],b[x])^g.flow(b[x],a[x]))
                        usededge[x]=true;
                }
            }
            dfs1(a[mne[i]]);
            printf("%d\n",(int)tmp.size());
            for(auto x:tmp)
                printf("%d ",x);
            puts("");
            return;
        }
    }
}
bool M2;
// g++ QOJ4809.cpp -std=c++14 -Wall -O2 -o QOJ4809
signed main() {
    // file_IO();
    int testcase=1;
    // scanf("%d",&testcase);
    while(testcase--)
        solve();
    debug("used time = %dms\n",(signed)(1000*clock()/CLOCKS_PER_SEC));
    debug("used memory = %dMB\n",(signed)((&M1-&M2)/1024/1024));
    return 0;
}

详细

Test #1:

score: 0
Wrong Answer
time: 0ms
memory: 12104kb

input:

5 7
1 2 1
1 3 -2
2 3 1
3 4 3
4 5 1
1 5 -1
2 5 2

output:

5
5
1 5 4 3 1 

result:

wrong answer Edge 1-1 does not appear in original graph