QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#354831#6560. Broken Minimum Spanning Treekevinshan#WA 1ms3552kbC++173.1kb2024-03-16 04:00:092024-03-16 04:00:10

Judging History

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

  • [2024-03-16 04:00:10]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3552kb
  • [2024-03-16 04:00:09]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define all(x) x.begin(), x.end()
#define pb push_back
#define f first
#define s second

#define FOR(i,a,b) for(int i=a;i<b;i++)
#define For(i,a) FOR(i,0,a)
#define pi pair<int,int>
#define trav(a,b) for(auto& a:b)

map<int,set<pi>> M;

int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0);
    if (fopen("input.in", "r")) {
        freopen("input.in", "r", stdin);
        freopen("output.out", "w", stdout);
    }
    int n;cin>>n;
    int curDepth=0, mxDep=0;
    For(i,n) {
        int s=0,t=0;
        string S;cin>>S;
        For(j,S.size()) {
            if(S[j]=='s') {
                s++;
            } else if(S[j]=='t') {
                t++;
            } else {
                if(S[j]=='}') {
                    curDepth--;
                }
                // cout << i << " " << s << " A " << t << curDepth << endl;
                mxDep = max(mxDep, curDepth);
                M[curDepth].insert({s,t});
                if(S[j]=='{') {
                    curDepth++;
                } else {
                    // curDepth--;
                }
            }
        }
        
    }
    // trav(x,M) {
    //     cout << x.f;
    //     trav(y,x.s) {
    //         cout << y.f << " " << y.s << " B ";
    //     }
    //     cout << endl;
    // }

    int tri = -1;
    For(i,n)if(M[i].size()>1) {
        pi A = *M[i].begin();
        pi B = *(++M[i].begin());
        if (tri==-1) {
            if(A.s==B.s) {
                cout << -1 << endl;
                return 0;
            } else {
                tri = (B.f-A.f)/(A.s-B.s);
            }
        }
    }
    // cout << "A " << tri << endl;
    if(tri==-1) {
        set<pi> diffs;
        For(i,mxDep-1) {
            assert(M[i].size()>0 && M[i+1].size()>0);
            pi A = *M[i].begin();
            pi B = *M[i+1].begin();
            diffs.insert({A.f-B.f,A.s-B.s});
        }
        if (diffs.size()<=1) {
            cout << 1 << endl;
            return 0;
        }
        pi A = *diffs.begin();
        pi B = *(++diffs.begin());
        if(B.s==A.s) {
            cout << -1 << endl;
            return 0;
        } else {
            tri = (B.f-A.f)/(A.s-B.s);
        }
    }
    bool works = true;
    if(tri<=0) {
        cout << -1 << endl;
        return 0;
    }
    assert(tri!=-1);
    
    vector<int> v;
    For(i,mxDep) {
        int need = -1;
        trav(x, M[i]){
            int sum = x.f + tri*x.s;
            if (need==-1) {
                need=sum;
            } else if(need!=sum) {
                works = false;
            }
        }
        assert(need!=-1);
        v.pb(need);
    }
    if(v.size()>1) {
        int K = v[1]-v[0];
        if(K<=0) {
            cout << -1 << endl;
            return 0;
        }
        For(i,v.size()-1) if(v[i+1]-v[i]!=K) {
            works = false;
        }
    }

    if(!works) {
        cout << -1 << endl;
    } else {
        cout << tri << endl;
    }

    
}


詳細信息

Test #1:

score: 0
Wrong Answer
time: 1ms
memory: 3552kb

input:

4 4
1 2 10
2 3 3
3 4 1
1 4 4

output:

1

result:

wrong output format Unexpected end of file - int32 expected