QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#305657	#5208. Jumbled Trees	LaStataleBlue	WA	1ms	3884kb	C++23	8.1kb	2024-01-15 19:53:30	2024-01-15 19:53:30

Judging History

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

[2024-01-15 19:53:30]
评测

测评结果：WA
用时：1ms
内存：3884kb

查看

[2024-01-15 19:53:30]
提交

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];
        x[col[i]] = b[i];
        rep(j,0,i) {
            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];
        assert(grafo[u][ind1][2]==id);
        assert(grafo[v][ind2][2]==id);
        
        grafo[u][ind1][1]=val;
        grafo[v][ind2][1]=val;
        curr[id].r=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);
    
    vector<int> opz;
    for(int i=0;i<e;i++){
        if(!st[i]){
            assert(curr[i].r==0);
            opz.push_back(i);
        }
    }
    
    random_shuffle(opz.begin(),opz.end());
    if(opz.size()>1)
        for(int x=0;x<(int)opz.size();x++){
        int i = opz[x];
        int j = opz[(x+1)%((int)opz.size())];
        
        //cout<<i<<" "<<j<<"\n";
        
        int rimi,rimj;
        
        cycle.clear();
        int u = edges[i][0];
        int v = edges[i][1];
        findcycle(findcycle,u,-1,v);
        
        set(i,true);
        rimi = cycle[rand()%cycle.size()];
        set(rimi,false);
        
        
        cycle.clear();
        u = edges[j][0];
        v = edges[j][1];
        findcycle(findcycle,u,-1,v);
        
        set(j,true);
        rimj = cycle[rand()%cycle.size()];
        set(rimj,false);
        
        A.push_back(curr);
        
        set(rimj,true);
        set(j,false);
        set(rimi,true);
        set(i,false);
    }
    
    /*
    if(opz.size()>2)
        for(int x=0;x<(int)opz.size();x+=2){
        int i = opz[x];
        int j = opz[(x+2)%((int)opz.size())];
        
        //cout<<i<<" "<<j<<"\n";
        
        int rimi,rimj;
        
        cycle.clear();
        int u = edges[i][0];
        int v = edges[i][1];
        findcycle(findcycle,u,-1,v);
        
        set(i,true);
        rimi = cycle[rand()%cycle.size()];
        set(rimi,false);
        
        
        cycle.clear();
        u = edges[j][0];
        v = edges[j][1];
        findcycle(findcycle,u,-1,v);
        
        set(j,true);
        rimj = cycle[rand()%cycle.size()];
        set(rimj,false);
        
        A.push_back(curr);
        
        set(rimj,true);
        set(j,false);
        set(rimi,true);
        set(i,false);
    }
    */
    while((int)A.size()<min(2*e,e+((int)opz.size())/2)){
        vector<int> opz;
        for(int i=0;i<e;i++){
            if(!st[i]){
                assert(curr[i].r==0);
                opz.push_back(i);
            }
        }
        if(opz.size()<=1)break;
        
        int i = opz[rand()%opz.size()];
        int j = i;
        while(j==i)j = opz[rand()%opz.size()];
        int rimi,rimj;
        
        cycle.clear();
        int u = edges[i][0];
        int v = edges[i][1];
        findcycle(findcycle,u,-1,v);
        
        set(i,true);
        rimi = cycle[rand()%cycle.size()];
        set(rimi,false);
        
        
        cycle.clear();
        u = edges[j][0];
        v = edges[j][1];
        findcycle(findcycle,u,-1,v);
        
        set(j,true);
        rimj = cycle[rand()%cycle.size()];
        set(rimj,false);
        
        A.push_back(curr);
        
        set(rimj,true);
        set(j,false);
        set(rimi,true);
        set(i,false);
    }
    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;
}

源文件, 语言: C++23

详细

Test #1:

score: 100

Accepted

time: 0ms

memory: 3672kb

input:

output:

result:

ok Participant found an answer (3 trees) and jury found an answer (5 trees)

Test #2:

score: 0

Accepted

time: 0ms

memory: 3588kb

input:

2 2 37
1 2 8
1 2 15

output:

2
15 2 
8 1

result:

ok Participant found an answer (2 trees) and jury found an answer (3 trees)

Test #3:

score: 0

Accepted

time: 0ms

memory: 3532kb

input:

output:

-1

result:

ok Both jury and participant did not find an answer

Test #4:

score: 0

Accepted

time: 0ms

memory: 3548kb

input:

output:

-1

result:

ok Both jury and participant did not find an answer

Test #5:

score: -100

Wrong Answer

time: 1ms

memory: 3884kb

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)