QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#305584#5208. Jumbled TreesLaStataleBlueWA 0ms3864kbC++235.7kb2024-01-15 17:27:292024-01-15 17:27:30

Judging History

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

  • [2024-01-15 17:27:30]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:3864kb
  • [2024-01-15 17:27:29]
  • 提交

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)