QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#305584 | #5208. Jumbled Trees | LaStataleBlue | WA | 0ms | 3864kb | C++23 | 5.7kb | 2024-01-15 17:27:29 | 2024-01-15 17:27:30 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
template<typename T> T bpow(T x, size_t n) {
if(n == 0) return T(1);
else{auto t=bpow(x, n/2); t=t*t; return n%2 ? x*t : t;}
}
int m;
struct modular {
int r; typedef modular mo;
modular(): r(0) {}
modular(int64_t rr): r(rr%m){if(r<0)r+=m;}
mo inv() const {return bpow(*this, m - 2);}
mo operator-()const{return r ? m - r : 0;}
mo operator*(const mo &t)const{return (ll)r*t.r%m;}
mo operator/(const mo &t)const{return *this*t.inv();}
mo operator+=(const mo &t){
r += t.r; if(r >= m) r -= m; return *this;}
mo operator-=(const mo &t){
r -= t.r; if(r < 0) r += m; return *this;}
mo operator+(const mo &t)const{return mo(*this)+=t;}
mo operator-(const mo &t)const{return mo(*this)-=t;}
mo operator*=(const mo &t){return *this=*this*t;}
bool operator==(const mo &t)const{return r==t.r;}
bool operator>(const mo &t)const{return r>t.r;}
bool operator<=(const double &t)const{return r<=int(t);}
bool operator>(const double &t)const{return r>int(t);}
};
modular fabs(modular x){return x.r;}
typedef modular T; //oppure modular<mod>
typedef vector<T> vd;
const double eps = 1e-12;
vi col; //globale per ricavare il sottospazio
int solveLinear(vector<vd>& A, vd& b, vd& x) {
int n = sz(A), m = sz(x), rank = 0, br, bc;
if (n) assert(sz(A[0]) == m);
col.resize(m); iota(all(col), 0);
rep(i,0,n) {
T v, bv = 0;
rep(r,i,n) rep(c,i,m)
if ((v = fabs(A[r][c])) > bv)
br = r, bc = c, bv = v;
if (bv <= eps) {
rep(j,i,n) if (fabs(b[j]) > eps) return -1;
break;
}
swap(A[i], A[br]); swap(b[i], b[br]);
swap(col[i], col[bc]);
rep(j,0,n) swap(A[j][i], A[j][bc]);
bv = T(1)/A[i][i];
rep(j,i+1,n) {
T fac = A[j][i] * bv;
b[j] -= fac * b[i];
rep(k,i+1,m) A[j][k] -= fac*A[i][k];
}
rank++;
}
x.assign(m, T(0));
for (int i = rank; i--;) {
b[i] = b[i]/A[i][i];
rep(z,i+1,m){ //(*)per ricavare il sottospazio
A[i][z] = A[i][z]/A[i][i];
}
x[col[i]] = b[i];
rep(j,0,i) {
rep(z,i+1,m){ //(*)per ricavare il sottospazio
A[j][z] -= A[j][i] * A[i][z];
}
b[j] -= A[j][i] * b[i];
}
}
return rank; // (multiple solutions if rank < m)
}
void solve(){
int n,e;
cin>>n>>e>>m;
vd b,x;
vector<vd> A;
vector<array<int,4>> edges(e);
vector ok(e,false),st(e,false);
vd curr(e);
vector grafo(n+1,vector<array<int,3>>());
for(int i=0;i<e;i++){
int u,v,x;
cin>>u>>v>>x;
b.push_back(x);
edges[i]={u,v,(int)grafo[u].size(),(int)grafo[v].size()};
grafo[u].push_back({v,false,i});
grafo[v].push_back({u,false,i});
}
auto set = [&](int id,bool val){
auto [u,v,ind1,ind2] = edges[id];
grafo[u][ind1][1]=val;
grafo[v][ind2][1]=val;
curr[id]=val;
};
vector vis=vector(n,false);
auto dfs = [&](auto &dfs,int nodo)->void{
vis[nodo]=true;
for(auto [to,act,id] : grafo[nodo]){
if(!vis[to]){
st[id]=true;
set(id,true);
dfs(dfs,to);
}
}
};
dfs(dfs,1);
vector<int> cycle;
auto findcycle = [&](auto &findcycle,int nodo,int last,int st)->bool{
if(nodo==st)return true;
bool res=false;
for(auto [to,act,id] : grafo[nodo]){
if(act && to!=last){
if(findcycle(findcycle,to,nodo,st)){
cycle.push_back(id);
res=true;
}
}
}
return res;
};
for(int i=0;i<e;i++){
if(!st[i]){
//cout<<"processo "<<i<<"\n";
cycle.clear();
auto [u,v] = tie(edges[i][0],edges[i][1]);
findcycle(findcycle,u,-1,v);
set(i,true);
for(auto j : cycle){
//cout<<j<<" ";
if(ok[j])continue;
ok[j]=true;
set(j,false);
A.push_back(curr);
set(j,true);
}
//cout<<"cicle \n";
set(i,false);
}
}
A.push_back(curr);
for(int i=0;i<e;i++){
if(!st[i]){
cycle.clear();
auto [u,v] = tie(edges[i][0],edges[i][1]);
findcycle(findcycle,u,-1,v);
set(i,true);
set(cycle[0],false);
A.push_back(curr);
}
}
vector tmp = vector(e,vd(A.size()));
for(int i=0;i<(int)A.size();i++){
for(int j=0;j<(int)A[i].size();j++){
tmp[j][i]=A[i][j];
}
}
swap(A,tmp);
x.resize(A[0].size());
if(solveLinear(A,b,x)==-1){
cout<<"-1\n";
}else{
cout<<x.size()<<"\n";
for(int i=0;i<(int)x.size();i++){
cout<<x[i].r<<" ";
for(int j=0;j<(int)tmp[i].size();j++)if(tmp[i][j]==1){
cout<<j+1<<" ";
}
cout<<"\n";
}
}
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
int t=1;
//cin>>t;
for(int i=1;i<=t;i++)solve();
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 3864kb
input:
3 3 101 1 2 30 2 3 40 3 1 50
output:
4 30 2 3 20 1 3 10 1 2 0 2 3
result:
ok Participant found an answer (4 trees) and jury found an answer (5 trees)
Test #2:
score: 0
Accepted
time: 0ms
memory: 3572kb
input:
2 2 37 1 2 8 1 2 15
output:
3 15 2 8 1 0 2
result:
ok Participant found an answer (3 trees) and jury found an answer (3 trees)
Test #3:
score: 0
Accepted
time: 0ms
memory: 3568kb
input:
5 4 5 1 3 1 2 3 2 2 5 3 4 1 4
output:
-1
result:
ok Both jury and participant did not find an answer
Test #4:
score: 0
Accepted
time: 0ms
memory: 3572kb
input:
10 15 997 4 3 459 9 7 94 9 8 767 10 2 877 5 8 258 3 4 166 8 5 621 8 10 619 9 1 316 10 5 516 3 10 125 1 7 961 3 6 500 4 10 976 3 4 842
output:
-1
result:
ok Both jury and participant did not find an answer
Test #5:
score: -100
Wrong Answer
time: 0ms
memory: 3648kb
input:
20 30 9973 1 10 696 3 8 2905 12 7 6609 20 10 1962 11 9 8430 19 2 412 6 3 6936 19 7 9113 14 15 5635 15 7 1770 13 10 3182 3 16 2625 17 1 7387 11 5 3700 9 15 1048 2 3 7717 12 10 8625 7 13 8141 5 14 2245 6 4 2819 18 19 8709 18 5 6191 17 10 7606 9 20 8626 17 4 8848 4 13 1073 10 8 2277 14 2 7714 11 8 5318...
output:
-1
result:
wrong answer Participant did not find an answer, while jury found (59 trees)