QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#108744#1359. Setting Mapsc20231020RE 998ms3608kbC++239.1kb2023-05-26 15:27:562023-05-26 15:27:57

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-05-26 15:27:57]
  • 评测
  • 测评结果：RE
  • 用时：998ms
  • 内存：3608kb
查看
  • [2023-05-26 15:27:56]
  • 提交

answer

/*
膜拜传奇特级宗师 Afterglow 大神儿
今天在 florr 首页称您为大夏尊贵的大名儿
一股敬佩之情油生然而
您在 florr 为国争光，扬我大夏威名
向您献上最真挚的膜拜！！！
膜拜传奇特级宗师 Afterglow 大神儿，今，一，您，扬。向！
膜拜传奇特级宗师 Afterglow 大神儿，今，一，您，扬。向！
膜拜传奇特级宗师 Afterglow 大神儿，今，一，您，扬。向！
*/
/*
          _____                    _____                     _____                    _____
         /\    \                  /\    \                   /\    \                  /\    \
        /  \    \                /  \    \                 /  \____\                /  \    \
        \   \    \              /    \    \               /   /    /                \   \    \
         \   \    \            /      \    \             /   /    /                  \   \    \
          \   \    \          /   /\   \    \           /   /____/                    \   \    \
           \   \    \        /   /  \   \    \         /    |    |                     \   \    \
            \   \    \      /   /    \   \    \       /     |    |                      \   \    \
             \   \    \    /   /    / \   \    \     /      |    |                       \   \    \
              \   \    \  /   /    /   \   \    \   /       |____|__ _____                \   \    \
_______________\   \____\/   /____/     \   \    \ /   /|            \    \ _______________\   \____\
\                  /    /\   \    \      \   \    \\  / |    _________\____\\                  /    /
 \    ____________/____/  \   \    \      \   \____\\/__|   |    |           \    ____________/____/
  \   \    \               \   \    \     |   |    |    |   |    |            \   \    \
   \   \    \               \   \    \    |   |    |    |   |    |             \   \    \
    \   \    \               \   \    \   |   |____|    |   |    |              \   \    \
     \   \    \               \   \    \  /   /    /    \   |    |               \   \    \
      \   \    \               \   \    \/   /    /      \  |    |                \   \    \
       \   \____\               \   \___/   /    /        \ |    |                 \   \____\
        \  /    /                \         /    /          \|    |                  \  /    /
         \/____/                  \_______/____/            \____|                   \/____/
*/
#define poj
#define zcz
#ifdef poj
//C++
#include<iomanip>
#include<iostream>
//C
#include<cassert>
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<ctime>
//STL
#include<algorithm>
#include<bitset>
#include<functional>
#include<map>
#include<queue>
#include<set>
#include<stack>
#include<string>
#include<vector>
//C++11
#if __cplusplus>=201103L
#include<chrono>
#include<random>
#include<unordered_set>
#include<unordered_map>
#endif
#else
#include<bits/stdc++.h>
#endif
using namespace std;
#ifdef zcz
class fastin{
	private:
#ifdef poj
	static const int MAXBF=1<<20;
#else
	const int MAXBF=1<<27;
#endif
	FILE *inf;
	char *inbuf,*inst,*ined;
	inline char _getchar(){
		if(inst==ined)inst=inbuf,ined=inbuf+fread(inbuf,1,MAXBF,inf);
		return inst==ined?EOF:*inst++;
	}
	public:
	fastin(FILE*_inf=stdin){
		inbuf=new char[MAXBF],inf=_inf,inst=inbuf,ined=inbuf;
	}
	~fastin(){delete inbuf;}
	template<typename Int> fastin&operator>>(Int &n){
		static char c;
		Int t=1;
		while((c=_getchar())<'0'||c>'9')if(c=='-')t=-1;
		n=(c^48);
		while((c=_getchar())>='0'&&c<='9')n=n*10+(c^48);
		n*=t;
		return *this;
	}
	fastin&operator>>(char&c){
		while((c=_getchar())<'!'||c>'~');
		return *this;
	}
	fastin&operator>>(char*s){
		int t=0;
		static char c;
		while((c=_getchar())==' '||c=='\n');
		s[t++]=c;
		while((c=_getchar())>='!'&&c<='~')s[t++]=c;
		s[t]='\0';
		return *this;
	}
}fi;
class fastout{
	private:
#ifdef poj
	static const int MAXBF=1<<20;
#else
	const int MAXBF=1<<27;
#endif
	FILE *ouf;
	char *oubuf,*oust,*oued;
	inline void _flush(){fwrite(oubuf,1,oued-oust,ouf);oued=oust;}
	inline void _putchar(char c){
		if(oued==oust+MAXBF)_flush(),oued=oubuf;
		*oued++=c;
		#ifdef local
		_flush();
		#endif
	}
	public:
	fastout(FILE*_ouf=stdout){
		oubuf=new char[MAXBF],ouf=_ouf,oust=oubuf,oued=oubuf;
	}
	~fastout(){_flush();delete oubuf;}
	template<typename Int> fastout&operator<<(Int n){
		if(n<0)_putchar('-'),n=-n;
		static char S[20];
		int t=0;
		do{S[t++]='0'+n%10,n/=10;}while(n);
		for(int i=0;i<t;++i)_putchar(S[t-i-1]);
		return *this;
	}
	fastout&operator<<(char c){_putchar(c);return *this;}
	fastout&operator<<(char*s){
		for(int i=0;s[i];++i)_putchar(s[i]);
		return *this;
	}
	fastout&operator<<(const char*s){
		for(int i=0;s[i];++i)_putchar(s[i]);
		return *this;
	}
}fo;
#define cin fi
#define cout fo
#else
#define czc ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#endif
#define mod7 1000000007
#define mod9 998244353
#define ll long long
#define isinf 0x3f3f3f3f
#define ilinf 0x7fffffff
#define lsinf 0x3f3f3f3f3f3f3f3f
#define llinf 0x7fffffffffffffff
#define pii pair<int,int>
#define fr first
#define sc second
#define next ___
#define pb push_back
#define N 4010
#define M 5000010
#define For(i,a,b) for(int i=(a);i<=(b);++i)
#define Rep(i,a,b,c) for(int i=(a);i<=(b);i+=c)
#define Per(i,a,b,c) for(int i=(a);i>=(b);i-=c)
#define Gra(i) for(int i=h[x];i;i=next[i])
typedef int arr[N];
typedef int arm[M];
typedef ll arl[N];
typedef ll alm[M];
typedef double ard[N];
typedef double adm[M];
namespace modint{
	template<typename Int,Int mod>
	struct modint{
		Int v;
		modint(){v=0;}
		modint(Int a){v=a;}
		bool operator==(modint a){return v==a.v;}
		bool operator!=(modint a){return v!=a.v;}
		bool operator<(modint a){return v<a.v;}
		bool operator>(modint a){return v>a.v;}
		bool operator<=(modint a){return v<=a.v;}
		bool operator>=(modint a){return v>=a.v;}
		bool operator==(Int a){return v==a;}
		bool operator!=(Int a){return v!=a;}
		bool operator<(Int a){return v<a;}
		bool operator>(Int a){return v>a;}
		bool operator<=(Int a){return v<=a;}
		bool operator>=(Int a){return v>=a;}
		modint operator+(modint a){return v>mod-a.v?v-mod+a.v:v+a.v;}
		modint operator-(modint a){return v>a.v?v-a.v:v+mod-a.v;}
		modint operator*(modint a){return v*a.v%mod;}
		modint operator+=(modint a){*this=*this+a;return *this;}
		modint operator-=(modint a){*this=*this-a;return *this;}
		modint operator*=(modint a){*this=*this*a;return *this;}
		modint qpow(modint a,Int b){
			modint r(1);
			for(;b;b>>=1,a*=a)if(b&1)r*=a;
			return r;
		}
		modint operator/(modint a){return qpow(a,mod-2)*v;}
		modint operator/=(modint a){*this=*this/a;return *this;}
		modint&operator++(){*this=*this+1;return *this;}
		modint&operator--(){*this=*this-1;return *this;}
		const modint operator++(int){modint r=*this;++*this;return r;}
		const modint operator--(int){modint r=*this;--*this;return r;}
		#ifdef cout
		friend fastout&operator<<(fastout&out,modint n){out<<n.v;return out;}
		#else
		friend ostream&operator<<(ostream&out,modint n){out<<n.v;return out;}
		#endif
	};
	typedef modint<long long,1000000007> int7;
	typedef modint<long long,998244353> int9;
}
using namespace modint;
int n,m,k,S,T,tot=1,s,t,tp;
arr next,to,h,w,dep,cur,in[6],out[6],p;
void add(int x,int y,int z){
//	cout<<x<<' '<<y<<' '<<z<<'\n';
	to[++tot]=y;
	next[tot]=h[x];
	h[x]=tot;
	w[tot]=z;
	to[++tot]=x;
	next[tot]=h[y];
	h[y]=tot;
	w[tot]=0;
}
int bfs(){
	fill(dep+1,dep+1+t,0);
	For(i,1,t)cur[i]=h[i];
	dep[s]=1;
	queue<int>q;
	q.push(s);
	while(q.size()){
		int x=q.front();
		q.pop();
		Gra(i){
			int y=to[i],z=w[i];
			if(!dep[y]&&z){
				dep[y]=dep[x]+1;
				if(y==t)return 1;
				q.push(y);
			}
		}
	}
	return 0;
}
int dfs(int x,int v){
//	cout<<x<<' '<<v<<'\n';
	if(!v||x==t)return v;
	int tem=v;
	for(int i=cur[x];i;i=next[i]){
		cur[x]=i;
		int y=to[i],z=w[i];
		if(dep[y]!=dep[x]+1)continue;
		int vt=dfs(y,min(z,tem));
		if(!vt)continue;
		w[i]-=vt;
		w[i^1]+=vt;
		tem-=vt;
		if(!tem)break;
	}
	if(tem==v)dep[x]=0;
	return v-tem;
}
void solve(){
	cin>>n>>m>>k>>S>>T;
	For(i,1,n){
		int x;
		cin>>x;
		For(j,0,k-1){
			in[j][i]=++s;
			out[j][i]=++s;
			add(s-1,s,x);
			if(j){
				add(in[j-1][i],s,isinf);
			}
		}
	}
	For(i,1,m){
		int x,y;
		cin>>x>>y;
		For(j,0,k-1){
			add(out[j][x],in[j][y],isinf);
		}
	}
	++s;
	t=s+1;
	add(s,in[0][S],isinf);
	For(i,0,k-1){
		add(out[i][T],t,isinf);
	}
	int ans=0;
	while(bfs())ans+=dfs(s,isinf);
//	cout<<ans<<'\n';
	if(ans>=isinf){
		cout<<"-1\n";
		return;
	}
	For(i,1,n){
		For(j,0,k-1){
			if(dep[in[j][i]]&&!dep[out[j][i]]){
				p[++tp]=i;
				break;
			}
		}
	}
	cout<<tp<<'\n';
	For(i,1,tp){
		cout<<p[i]<<' ';
	}
	return;
}
int main(){
	#ifndef zcz
	czc;
	#endif
	timespec time1,time2;
	clock_gettime(CLOCK_REALTIME,&time1);
	int t=1;
	while(t--)solve();
	clock_gettime(CLOCK_REALTIME,&time2);
	while(1000000000ll*(time2.tv_sec-time1.tv_sec)+1ll*(time2.tv_nsec-time1.tv_nsec)<=996000000ll)clock_gettime(CLOCK_REALTIME,&time2);
	return 0;
}
Source code, Language: C++23

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 998ms
memory: 3552kb

input:

3 2 5
1 3
1 60 35
1 2
2 3

output:

-1

result:

ok answer = IMPOSSIBLE

Test #2:

score: 0
Accepted
time: 997ms
memory: 3444kb

input:

7 11 1
1 7
100 5 7 16 11 12 100
1 2
1 3
1 4
1 5
2 3
2 6
3 6
4 3
4 7
5 7
6 7

output:

4
2 3 4 5

result:

ok answer = 39

Test #3:

score: 0
Accepted
time: 994ms
memory: 3472kb

input:

11 17 2
1 11
1000 10 10 10 10 10 10 10 10 10 1000
1 2
1 3
1 4
1 5
1 6
2 7
3 7
4 7
5 8
6 8
7 8
7 9
7 10
8 9
8 11
9 11
10 11

output:

6
5 6 7 8 9 10

result:

ok answer = 60

Test #4:

score: 0
Accepted
time: 994ms
memory: 3528kb

input:

2 2 2
2 1
100 200
1 2
2 1

output:

2
1 2

result:

ok answer = 300

Test #5:

score: 0
Accepted
time: 998ms
memory: 3536kb

input:

5 5 5
1 5
1 1 1 1 1
1 2
2 3
3 4
4 5
1 5

output:

-1

result:

ok answer = IMPOSSIBLE

Test #6:

score: 0
Accepted
time: 989ms
memory: 3608kb

input:

100 120 5
1 5
5367720 2854323 1799056 9744604 3215334 7580413 6269402 3208439 8812449 3297484 2047196 4044341 7514502 2928715 9335004 3935096 6660663 3356480 4801491 5786147 895995 6710240 222342 4469390 1543213 6678041 8838445 6741919 8138951 5273670 8983795 5131484 4245746 7460466 8357966 8464419 ...

output:

-1

result:

ok answer = IMPOSSIBLE

Test #7:

score: 0
Accepted
time: 998ms
memory: 3500kb

input:

2 1 5
1 2
10 10
1 2

output:

-1

result:

ok answer = IMPOSSIBLE

Test #8:

score: 0
Accepted
time: 997ms
memory: 3552kb

input:

154 304 2
67 7
10000000 10000000 10000000 10000000 10000000 10000000 10000000 10000000 10000000 10000000 10000000 10000000 10000000 10000000 10000000 10000000 10000000 10000000 10000000 10000000 10000000 10000000 10000000 10000000 10000000 10000000 10000000 10000000 10000000 10000000 10000000 100000...

output:

2
7 67

result:

ok answer = 20000000

Test #9:

score: 0
Accepted
time: 993ms
memory: 3424kb

input:

75 146 1
15 2
10000000 10000000 10000000 10000000 10000000 10000000 10000000 10000000 10000000 10000000 10000000 10000000 10000000 10000000 10000000 10000000 10000000 10000000 10000000 10000000 10000000 10000000 10000000 10000000 10000000 10000000 10000000 10000000 10000000 10000000 10000000 1000000...

output:

1
15

result:

ok answer = 10000000

Test #10:

score: -100
Runtime Error

input:

182 360 4
97 110
10000000 10000000 10000000 10000000 10000000 10000000 10000000 10000000 10000000 10000000 10000000 10000000 10000000 10000000 10000000 10000000 10000000 10000000 10000000 10000000 10000000 10000000 10000000 10000000 10000000 10000000 10000000 10000000 10000000 10000000 10000000 1000...

output:

result:
English 繁體中文 简体中文

Server Time: 2025-01-20 21:58:34 | OpenSource Project