QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #309744 | #8128. Alternating Paths | ucup-team266# | Compile Error | / | / | C++20 | 5.6kb | 2024-01-20 20:21:30 | 2024-01-20 20:21:30 |
Judging History
answer
/*
Things to notice:
1. do not calculate useless values
2. do not use similar names
Things to check:
1. submit the correct file
2. time (it is log^2 or log)
3. memory
4. prove your naive thoughts
5. long long
6. corner case like n=0,1,inf or n=m
7. check if there is a mistake in the ds or other tools you use
8. fileio in some oi-contest
9. module on time
10. the number of a same divisor in a math problem
11. multi-information and queries for dp and ds problems
*/
#pragma GCC optimize("Ofast")
#pragma GCC target("avx")
#pragma GCC optimize("unroll-loops")
#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pii pair<int,int>
#define mp make_pair
#define pb push_back
const int mod=998244353;
const int inf=0x3f3f3f3f;
int n,m,U[305],V[305],col[305],perm[305];
int fa[105];
int find(int x)
{
if(fa[x]==x) return x;
return fa[x]=find(fa[x]);
}
void merge(int x,int y)
{
int xx=find(x),yy=find(y);
if(xx!=yy) fa[xx]=yy;
}
mt19937 rnd(114514);
int vis[105][2];
vector <pii > g[105];
bool chk()
{
for(int i=1;i<=n;i++) g[i].clear();
for(int i=1;i<=m;i++) g[U[i]].pb(mp(V[i],col[i])),g[V[i]].pb(mp(U[i],col[i]));
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++) vis[j][0]=vis[j][1]=0;
vis[i][0]=vis[i][1]=1;
queue <pii > q;
q.push(mp(i,0)),q.push(mp(i,1));
while(q.size())
{
int u=q.front().fi,c=q.front().se;
q.pop();
for(int j=0;j<g[u].size();j++) if(g[u][j].se!=c)
{
int v=g[u][j].fi;
if(vis[v][c^1]) continue;
vis[v][c^1]=1,q.push(mp(v,(c^1)));
}
}
for(int j=1;j<=n;j++) if(!vis[j][0]&&!vis[j][1]) return 0;
}
return 1;
}
int tr[305],dep[305];
void dfs0(int u,int par)
{
for(int i=0;i<g[u].size();i++)
{
int v=g[u][i].fi;
if(v==par) continue;
dep[v]=dep[u]+1,dfs0(v,u);
}
}
bool work()
{
for(int i=1;i<=n;i++) fa[i]=i,g[i].clear(),dep[i]=0;
for(int i=1;i<=m;i++) perm[i]=i,tr[i]=0;
for(int i=m;i>=1;i--) swap(perm[i],perm[1+rnd()%i]);
for(int i=1;i<=m;i++)
{
int x=perm[i];
if(find(U[x])!=find(V[x])) merge(U[x],V[x]),tr[x]=1,g[U[x]].pb(mp(V[x],x)),g[V[x]].pb(mp(U[x],x));
}
dfs0(1+rnd()%n,-1);
for(int i=1;i<=m;i++)
{
if(tr[i]) col[i]=min(dep[U[i]],dep[V[i]])%2;
else
{
col[i]=rnd()%2;
int x=U[i],y=V[i];
if(rnd()%2) swap(x,y);
col[i]=(dep[x]%2)^1;
}
}
// for(int i=1;i<=m;i++) cout<<col[i];
// cout<<"\n";
// system("pause");
if(chk())
{
for(int i=1;i<=m;i++) cout<<(col[i]?"R":"B");
cout<<"\n";
return 1;
}
return 0;
}
void solve()
{
cin>>n>>m;
for(int i=1;i<=m;i++) cin>>U[i]>>V[i];
for(int _=0;_<30000;_++) if(work()) return;
cout<<"IMPOSSIBLE\n";
}
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0);
int _=1;
cin>>_;
while(_--) solve();
return 0;
}/*
Things to notice:
1. do not calculate useless values
2. do not use similar names
Things to check:
1. submit the correct file
2. time (it is log^2 or log)
3. memory
4. prove your naive thoughts
5. long long
6. corner case like n=0,1,inf or n=m
7. check if there is a mistake in the ds or other tools you use
8. fileio in some oi-contest
9. module on time
10. the number of a same divisor in a math problem
11. multi-information and queries for dp and ds problems
*/
#pragma GCC optimize("Ofast")
#pragma GCC target("avx")
#pragma GCC optimize("unroll-loops")
#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pii pair<int,int>
#define mp make_pair
#define pb push_back
const int mod=998244353;
const int inf=0x3f3f3f3f;
int n,m,U[305],V[305],col[305],perm[305];
int fa[105];
int find(int x)
{
if(fa[x]==x) return x;
return fa[x]=find(fa[x]);
}
void merge(int x,int y)
{
int xx=find(x),yy=find(y);
if(xx!=yy) fa[xx]=yy;
}
mt19937 rnd(114514);
int vis[105][2];
vector <pii > g[105];
bool chk()
{
for(int i=1;i<=n;i++) g[i].clear();
for(int i=1;i<=m;i++) g[U[i]].pb(mp(V[i],col[i])),g[V[i]].pb(mp(U[i],col[i]));
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++) vis[j][0]=vis[j][1]=0;
vis[i][0]=vis[i][1]=1;
queue <pii > q;
q.push(mp(i,0)),q.push(mp(i,1));
while(q.size())
{
int u=q.front().fi,c=q.front().se;
q.pop();
for(int j=0;j<g[u].size();j++) if(g[u][j].se!=c)
{
int v=g[u][j].fi;
if(vis[v][c^1]) continue;
vis[v][c^1]=1,q.push(mp(v,(c^1)));
}
}
for(int j=1;j<=n;j++) if(!vis[j][0]&&!vis[j][1]) return 0;
}
return 1;
}
int tr[305],dep[305];
void dfs0(int u,int par)
{
for(int i=0;i<g[u].size();i++)
{
int v=g[u][i].fi;
if(v==par) continue;
dep[v]=dep[u]+1,dfs0(v,u);
}
}
bool work()
{
for(int i=1;i<=n;i++) fa[i]=i,g[i].clear(),dep[i]=0;
for(int i=1;i<=m;i++) perm[i]=i,tr[i]=0;
for(int i=m;i>=1;i--) swap(perm[i],perm[1+rnd()%i]);
for(int i=1;i<=m;i++)
{
int x=perm[i];
if(find(U[x])!=find(V[x])) merge(U[x],V[x]),tr[x]=1,g[U[x]].pb(mp(V[x],x)),g[V[x]].pb(mp(U[x],x));
}
dfs0(1+rnd()%n,-1);
for(int i=1;i<=m;i++)
{
if(tr[i]) col[i]=min(dep[U[i]],dep[V[i]])%2;
else
{
col[i]=rnd()%2;
// int x=U[i],y=V[i];
// if(rnd()%2) swap(x,y);
// col[i]=(dep[x]%2);
}
}
// for(int i=1;i<=m;i++) cout<<col[i];
// cout<<"\n";
// system("pause");
if(chk())
{
for(int i=1;i<=m;i++) cout<<(col[i]?"R":"B");
cout<<"\n";
return 1;
}
return 0;
}
void solve()
{
cin>>n>>m;
for(int i=1;i<=m;i++) cin>>U[i]>>V[i];
for(int _=0;_<30000;_++) if(work()) return;
cout<<"IMPOSSIBLE\n";
}
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0);
int _=1;
cin>>_;
while(_--) solve();
return 0;
}
详细
answer.code:162:11: error: redefinition of ‘const int mod’
162 | const int mod=998244353;
| ^~~
answer.code:31:11: note: ‘const int mod’ previously defined here
31 | const int mod=998244353;
| ^~~
answer.code:163:11: error: redefinition of ‘const int inf’
163 | const int inf=0x3f3f3f3f;
| ^~~
answer.code:32:11: note: ‘const int inf’ previously defined here
32 | const int inf=0x3f3f3f3f;
| ^~~
answer.code:164:5: error: redefinition of ‘int n’
164 | int n,m,U[305],V[305],col[305],perm[305];
| ^
answer.code:33:5: note: ‘int n’ previously declared here
33 | int n,m,U[305],V[305],col[305],perm[305];
| ^
answer.code:164:7: error: redefinition of ‘int m’
164 | int n,m,U[305],V[305],col[305],perm[305];
| ^
answer.code:33:7: note: ‘int m’ previously declared here
33 | int n,m,U[305],V[305],col[305],perm[305];
| ^
answer.code:164:9: error: redefinition of ‘int U [305]’
164 | int n,m,U[305],V[305],col[305],perm[305];
| ^
answer.code:33:9: note: ‘int U [305]’ previously declared here
33 | int n,m,U[305],V[305],col[305],perm[305];
| ^
answer.code:164:16: error: redefinition of ‘int V [305]’
164 | int n,m,U[305],V[305],col[305],perm[305];
| ^
answer.code:33:16: note: ‘int V [305]’ previously declared here
33 | int n,m,U[305],V[305],col[305],perm[305];
| ^
answer.code:164:23: error: redefinition of ‘int col [305]’
164 | int n,m,U[305],V[305],col[305],perm[305];
| ^~~
answer.code:33:23: note: ‘int col [305]’ previously declared here
33 | int n,m,U[305],V[305],col[305],perm[305];
| ^~~
answer.code:164:32: error: redefinition of ‘int perm [305]’
164 | int n,m,U[305],V[305],col[305],perm[305];
| ^~~~
answer.code:33:32: note: ‘int perm [305]’ previously declared here
33 | int n,m,U[305],V[305],col[305],perm[305];
| ^~~~
answer.code:165:5: error: redefinition of ‘int fa [105]’
165 | int fa[105];
| ^~
answer.code:34:5: note: ‘int fa [105]’ previously declared here
34 | int fa[105];
| ^~
answer.code:166:5: error: redefinition of ‘int find(int)’
166 | int find(int x)
| ^~~~
answer.code:35:5: note: ‘int find(int)’ previously defined here
35 | int find(int x)
| ^~~~
answer.code:171:6: error: redefinition of ‘void merge(int, int)’
171 | void merge(int x,int y)
| ^~~~~
answer.code:40:6: note: ‘void merge(int, int)’ previously defined here
40 | void merge(int x,int y)
| ^~~~~
answer.code:176:9: error: redefinition of ‘std::mt19937 rnd’
176 | mt19937 rnd(114514);
| ^~~
answer.code:45:9: note: ‘std::mt19937 rnd’ previously declared here
45 | mt19937 rnd(114514);
| ^~~
answer.code:178:5: error: redefinition of ‘int vis [105][2]’
178 | int vis[105][2];
| ^~~
answer.code:47:5: note: ‘int vis [105][2]’ previously declared here
47 | int vis[105][2];
| ^~~
answer.code:179:15: error: redefinition of ‘std::vector<std::pair<int, int> > g [105]’
179 | vector <pii > g[105];
| ^
answer.code:48:15: note: ‘std::vector<std::pair<int, int> > g [105]’ previously defined here
48 | vector <pii > g[105];
| ^
answer.code:180:6: error: redefinition of ‘bool chk()’
180 | bool chk()
| ^~~
answer.code:49:6: note: ‘bool chk()’ previously defined here
49 | bool chk()
| ^~~
answer.code:205:5: error: redefinition of ‘int tr [305]’
205 | int tr[305],dep[305];
| ^~
answer.code:74:5: note: ‘int tr [305]’ previously declared here
74 | int tr[305],dep[305];
| ^~
answer.code:205:13: error: redefinition of ‘int dep [305]’
205 | int tr[305],dep[305];
| ^~~
answer.code:74:13: note: ‘int dep [305]’ previously declared here
74 | int tr[305],dep[305];
| ^~~
answer.code:206:6: error: redefinition of ‘void dfs0(int, int)’
206 | void dfs0(int u,int par)
| ^~~~
answer.code:75:6: note: ‘void dfs0(int, int)’ previously defined here
75 | void dfs0(int u,int par)
| ^~~~
answer.code:215:6: error: redefinition of ‘bool work()’
215 | bool work()
| ^~~~
answer.code:84:6: note: ‘bool work()’ previously defined here
84 | bool work()
| ^~~~
answer.code:248:6: error: redefinition of ‘void solve()’
248 | void solve()
| ^~~~~
answer.code:117:6: note: ‘void solve()’ previously defined here
117 | void solve()
| ^~~~~
answer.code:255:8: error: redefinition of ‘int main()’
255 | signed main()
| ^~~~
answer.code:124:8: note: ‘int main()’ previously defined here
124 | signed main()
| ^~~~