QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#227608 | #7640. Colorful Cycles | ucup-team1447# | WA | 226ms | 193820kb | C++14 | 3.1kb | 2023-10-27 19:39:16 | 2023-10-27 19:39:17 |
Judging History
answer
// what is matter? never mind.
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
//#pragma GCC target("sse,sse2,sse3,sse4,popcnt,abm,mmx,avx,avx2")
#include<bits/stdc++.h>
#define For(i,a,b) for(int i=(a);i<=(b);++i)
#define Rep(i,a,b) for(int i=(a);i>=(b);--i)
#define ll long long
#define ull unsigned long long
//#define int long long
using namespace std;
inline int read()
{
char c=getchar();int x=0;bool f=0;
for(;!isdigit(c);c=getchar())f^=!(c^45);
for(;isdigit(c);c=getchar())x=(x<<1)+(x<<3)+(c^48);
if(f)x=-x;return x;
}
#define fi first
#define se second
#define pb push_back
#define mkp make_pair
typedef pair<int,int>pii;
typedef vector<int>vi;
#define maxn 2000005
#define inf 0x3f3f3f3f
int n,m,w[maxn],uu[maxn],vv[maxn],id[maxn];
bool ok=0;
vi e[maxn];
vi g[maxn];
int dfn[maxn],low[maxn],stk[maxn],tp,idx,scc;
void tar(int u,int pa){
dfn[u]=low[u]=++idx,stk[++tp]=u;
for(auto v:e[u]){
if(!dfn[v]){
tar(v,u),low[u]=min(low[u],low[v]);
if(low[v]>=dfn[u]){
g[++scc].pb(u);
while(stk[tp+1]!=v)g[scc].pb(stk[tp--]);
}
}
else if(v!=pa)low[u]=min(low[u],dfn[v]);
}
if(!e[u].size()) g[++scc].pb(u);
}
namespace G{
int n;
map<int,int>e[maxn];
int rake(int x,int y){
if(!ok){
For(i,0,7)if(x>>i&1)
For(j,0,7)if((y>>j&1) && ((i|j)==7))ok=1;
}
return x|y;
}
int compress(int x,int y){
int z=0;
For(i,0,7)if(x>>i&1)
For(j,0,7)if(y>>j&1)z|=(1<<(i|j));
return z;
}
void add(int u,int v,int w){
if(e[u].count(v)) e[u][v]=e[v][u]=rake(w,e[u][v]);
else e[u][v]=e[v][u]=w;
}
queue<int>q;
void chk(int u){
if(e[u].size()<=2) q.push(u);
}
void solve()
{
//cout<<"sol "<<n<<"\n";
For(i,1,n) chk(i);
while(q.size()){
int u=q.front();q.pop();
if(!e[u].size())continue;//cout<<"del "<<u<<"\n";
for(auto it:e[u])e[it.fi].erase(u);
if(e[u].size()==2){
int v1=(e[u].begin()->fi),w1=(e[u].begin()->se);
int v2=((--e[u].end())->fi),w2=((--e[u].end())->se);
add(v1,v2,compress(w1,w2));
}
for(auto it:e[u])chk(it.fi);
e[u].clear();
}
For(i,1,n){
if(e[i].size())ok=1;
e[i].clear();
}
}
void clear(){
For(i,0,n) e[i].clear();
}
}
void work()
{
n=read(),m=read();ok=0;
For(i,0,n+m+1)e[i].clear(),g[i].clear(),dfn[i]=low[i]=0; idx=tp=scc=0;
For(i,0,n+m+1)stk[i]=0;
For(i,1,m){
int u=read(),v=read();
w[i]=read()-1;
uu[i]=u,vv[i]=v;
e[u].pb(i+n),e[i+n].pb(u);
e[v].pb(i+n),e[i+n].pb(v);
}
For(i,1,n)if(!dfn[i])tar(i,0);
For(i,1,scc){
if(ok)break;
int sta=0;
idx=0;
for(int u:g[i]) if(u<=n) id[u]=++idx;
G::n=idx;
for(int j:g[i]) if(j>n){
j-=n;
// cout<<"j: "<<j<<" "<<w[j]<<"\n";
G::add(id[uu[j]],id[vv[j]],(1<<(1<<w[j])));
sta|=(1<<w[j]);
}
// cout<<"sta "<<sta<<"\n";
if(sta!=7){
G::clear();
continue;
}
G::solve();
G::clear();
}
if(ok)puts("Yes");
else puts("No");
}
signed main()
{
int T=read();
while(T--)work();
return 0;
}
/*
1
7 9
1 3 1
3 2 1
1 4 2
4 2 2
1 5 3
5 6 3
5 7 3
7 6 2
6 2 3
4 4
1 2 1
2 3 2
3 4 3
1 4 1
5 6
1 2 1
2 3 1
1 3 2
3 4 3
3 5 3
4 5 1
*/
詳細信息
Test #1:
score: 100
Accepted
time: 23ms
memory: 193820kb
input:
2 3 3 1 2 3 2 3 1 1 3 2 5 6 1 2 1 2 3 1 1 3 2 3 4 3 3 5 3 4 5 3
output:
Yes No
result:
ok 2 token(s): yes count is 1, no count is 1
Test #2:
score: -100
Wrong Answer
time: 226ms
memory: 193524kb
input:
100000 7 10 7 2 2 6 4 2 6 1 2 7 1 3 3 4 1 6 7 1 2 6 3 3 1 2 5 3 1 2 1 1 7 10 5 7 3 7 1 1 4 6 3 6 3 1 3 4 3 4 2 2 3 2 3 1 3 3 3 7 1 1 4 2 7 10 5 6 3 3 5 2 7 2 3 7 3 3 1 2 2 4 3 2 7 4 2 6 1 2 2 6 1 7 5 2 7 10 7 1 3 7 5 3 6 4 1 7 6 1 1 4 1 3 4 2 2 7 2 1 3 1 3 5 3 5 1 3 7 10 6 7 2 3 4 3 1 4 2 5 3 2 7 4 ...
output:
Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes No Yes Yes Yes Yes Yes No Yes Yes Yes Yes Yes Yes Yes Yes Yes No Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes No ...
result:
wrong answer expected NO, found YES [490th token]