QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#783217 | #9810. Obliviate, Then Reincarnate | comp_towels_cat | TL | 307ms | 39768kb | C++20 | 6.0kb | 2024-11-26 01:37:38 | 2024-11-26 01:37:39 |
Judging History
This is the latest submission verdict.
- [2024-11-26 23:19:26]
- hack成功,自动添加数据
- (/hack/1260)
- [2024-11-26 01:37:38]
- Submitted
answer
// #pragma GCC optimize(3)
// #pragma GCC optimize("Ofast")
// #pragma GCC optimize("inline")
// #pragma GCC optimize("omit-frame-pointer")
#include<bits/stdc++.h>
// #include<bits/extc++.h>
#define rep(a,b,c) for (int a=b;a<=c;a++)
#define repll(a,b,c) for (LL a=b;a<=c;a++)
#define per(a,b,c) for (int a=b;a>=c;a--)
#define perll(a,b,c) for (LL a=b;a>=c;a--)
#define repIt(it,ctner) for (auto it=ctner.begin();it!=ctner.end();it++)
#define perIt(it,ctner) for (auto it=ctner.rbegin();it!=ctner.rend();it++)
#define repAdj(i,h,ne,u) for(int i=h[u];i;i=ne[i])
#define setValue(ctner,val) memset(ctner,val,sizeof ctner)
#define all(ctner) ctner.begin(),ctner.end()
#define output(a,b,c) cout<<a<<" "<<b<<" "<<c<<"\n";
#define ft first
#define sd second
using namespace std;
// using namespace __gnu_cxx;
// using namespace __gnu_pbds;
typedef long long LL;
typedef long long ll;
typedef unsigned long long ULL;
typedef unsigned long long ull;
typedef __int128 LLL;
typedef __int128 lll;
typedef long double LD;
typedef pair<LL,LL> PLL;
typedef pair<int,int> PII;
typedef pair<int,LL> PIL;
typedef pair<LL,int> PLI;
typedef pair<double,int> PDI;
typedef vector<int> VI;
//use cin
void LLLread(LLL &x){
string s;cin>>s;
x=0;int f=1;
if(s[0]=='-') f=-1,s=s.substr(1);
for(auto c:s) x=x*10+c-'0';
x*=f;
}
//use cout
void LLLwrite(LLL x){
if(x<0) cout<<'-',x=-x;
if(x==0) cout<<0;
vector<char> v;
while(x) v.push_back(x%10+'0'),x/=10;
reverse(v.begin(),v.end());
for(auto c:v) cout<<c;
}
ostream& operator<<(ostream& os,const LLL& x){
LLLwrite(x);
return os;
}
istream& operator>>(istream& is,LLL& x){
LLLread(x);
return is;
}
//random
LL rnd(const LL &mn = 0, const LL &mx = 100) {
LL x = mn + ((rand()<<15) + rand()) % (mx - mn + 1);
return x;
};
//gcd
LL gcd(LL a,LL b){
return __gcd(a,b);
}
//lcm
LL lcm(LL a,LL b){
return a/__gcd(a,b)*b;
}
int _T=1;
const int N=5e5+5,M=3*N;
const LL mod1=998244353,mod2=1e9+7;
const int imod[4]={39983,39989,39979,39971};
const LL MAXLL=1e18;
const int MAXINT=1e9+1;
const long double pi=acos(-1.0);
const long double eps=1e-10;
//const double phi=(1+sqrt(5))/2;
const string alphabet="abcdefghijklmnopqrstuvwxyz";
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const LL mod=mod2;
int highbit(LL x){
return 63-__builtin_clzll(x);
}
void init(){
}
LL n,m,q;
queue<int> ans;
vector<PIL> G[N],G2[N];
//Kosaraju to get scc
bool vis[N];
int color[N],scc_cnt;
vector<int> scc[N],S;
void dfs1(int u){
vis[u]=1;
for(auto [v,w]:G[u]){
if(vis[v]) continue;
dfs1(v);
}
S.push_back(u);
}
void dfs2(int u){
color[u]=scc_cnt;
scc[scc_cnt].push_back(u);
for(auto [v,w]:G2[u]){
if(color[v]) continue;
dfs2(v);
}
}
void kosaraju(){
rep(i,0,n-1){
if(vis[i]) continue;
dfs1(i);
}
perIt(it,S){
if(color[*it]) continue;
scc_cnt++;
dfs2(*it);
}
// rep(i,1,scc_cnt){
// cout<<"scc "<<i<<" : ";
// for(auto u:scc[i]){
// cout<<u<<" ";
// }
// cout<<"\n";
// }
}
LL dist[N];
int cnt[N],constra[N];
bool spfa(int u,int szscc){
queue<int> q;
q.push(u);
dist[u]=0;
vis[u]=1;
// cout<<"szscc is "<<szscc<<"\n";
while(!q.empty()){
u=q.front();q.pop();
vis[u]=0;
for(auto [v,w]:G[u]){
if(constra[v]) continue;
if(dist[v]>dist[u]+w){
// cout<<u<<" -> "<<v<<" is "<<w<<"\n";
dist[v]=dist[u]+w;
cnt[v]=cnt[u]+1;
// cout<<v<<" : "<<dist[v]<<" "<<cnt[v]<<"\n";
if(cnt[v]>=szscc) return 0;
if(!vis[v]){
vis[v]=1;
q.push(v);
}
}
}
}
return 1;
}
// 0 1 1000000000
// 1 0 -1000000000
void getans(){
rep(i,1,scc_cnt){
if(scc[i].size()<=1) continue;
// cout<<"scc "<<i<<" : ";
for(auto u:scc[i]){
vis[u]=0;
constra[u]=0;
cnt[u]=0;
dist[u]=MAXLL;
// cout<<u<<" ";
}
// cout<<"\n";
int jud=spfa(scc[i][0],scc[i].size());
for(auto u:scc[i]){
vis[u]=1;
constra[u]=1;
cnt[u]=0;
dist[u]=MAXLL;
}
if(!jud){
// cout<<scc[i][0]<<" is a good node\n";
ans.push(scc[i][0]);
}
}
// cout<<"\n";
}
void bfs(){
while(!ans.empty()){
int u=ans.front();ans.pop();
if(vis[u]) continue;
vis[u]=1;
for(auto [v,w]:G2[u]){
if(!vis[v]){
ans.push(v);
}
}
}
}
void solve(){
cin>>n>>m>>q;
rep(i,1,m){
LL a,b;
cin>>a>>b;
LL u=a,v=a+b,w=b;
u=(u%n+n)%n;
v=(v%n+n)%n;
// cout<<u<<" "<<v<<" "<<w<<"\n";
if(u==v){
if(w) ans.push(u);
continue;
}
G[u].push_back({v,w});
G2[v].push_back({u,w});
}
kosaraju();
rep(i,0,n-1){
int u=i;
vis[u]=1;
constra[u]=1;
cnt[u]=0;
dist[u]=MAXLL;
}
getans();
rep(i,0,n-1){
repIt(it,G[i]){
LL w=it->sd;
it->sd=-w;
}
}
getans();
rep(i,0,n-1){
vis[i]=0;
}
bfs();
rep(i,1,q){
LL x;
cin>>x;
LL u=(x%n+n)%n;
if(vis[u]) cout<<"Yes\n";
else cout<<"No\n";
}
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
srand(time(0));
// cin>>_T;
init();
rep(i,1,_T){
solve();
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 3ms
memory: 7856kb
input:
3 2 3 1 1 -1 3 1 2 3
output:
Yes Yes No
result:
ok 3 tokens
Test #2:
score: 0
Accepted
time: 0ms
memory: 7764kb
input:
3 2 3 1 1 -1 0 1 2 3
output:
No No No
result:
ok 3 tokens
Test #3:
score: 0
Accepted
time: 0ms
memory: 8076kb
input:
1 1 1 0 1000000000 -1000000000
output:
Yes
result:
ok "Yes"
Test #4:
score: 0
Accepted
time: 3ms
memory: 7760kb
input:
3 2 3 0 1000000000 1 -1000000000 -1000000000 0 -1000000000
output:
No No No
result:
ok 3 tokens
Test #5:
score: 0
Accepted
time: 307ms
memory: 39768kb
input:
50134 500000 500000 -154428638 -283522863 -186373509 -327130969 154999046 46750274 -933523447 349415487 -437683609 140099255 864996699 -262318199 811293034 -264299324 120273173 52410685 874944410 -52048424 445049930 -803690605 -138111276 -104634331 720288580 126597671 471164416 -348777147 -356502322...
output:
No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No ...
result:
ok 500000 tokens
Test #6:
score: -100
Time Limit Exceeded
input:
100848 500000 500000 720352587 361776806 231853504 -933882325 960971230 -83519300 -152772415 -631132247 842871215 -666621297 857194330 -754943024 -698506963 -705416545 -3551931 -927937446 628710320 -942247987 674921043 847145884 -325629529 475694308 -339363446 686789318 236702996 654762989 420412365...