QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#717493#9230. Routing K-Codesgates_orzWA 341ms32920kbC++204.3kb2024-11-06 18:07:192024-11-06 18:07:19

Judging History

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

  • [2024-11-06 18:07:19]
  • 评测
  • 测评结果:WA
  • 用时:341ms
  • 内存:32920kb
  • [2024-11-06 18:07:19]
  • 提交

answer

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

using LL=long long;
const int N=2e5+10;
const int M=N*2;
#define int LL
int n,m;
const LL INF=4294967296;

int h[N],e[M],ne[M],idx;
void add(int a,int b) {
    e[idx]=b;
    ne[idx]=h[a];
    h[a]=idx++;
}
int len;
int root1,root2;
int root;
int dep[N],f[N];
int f2[N];
int d[N];
void dfs(int u,int fat) {
    dep[u]=dep[fat]+1;
    f[u]=fat;
    if(len<dep[u])len=dep[u],root=u;
    for(int i=h[u];i!=-1;i=ne[i]) {
        int v=e[i];
        if(v==fat)continue;
        dfs(v,u);
    }
}
void dfs3(int u,int fat) {
    f2[u]=fat;
    for(int i=h[u];i!=-1;i=ne[i]) {
        int v=e[i];
        if(v==fat)continue;
        dfs3(v,u);
    }
}
LL val[N];
bool work(LL x,int root1,int root2,int f[]) {
    set<LL>st;
    vector<int>vis(n+1,0);
    int u=root2;
    while(u!=root1) {
        val[u]=x;
        vis[u]=1;
        st.insert(x);
        if(x)x*=2;
        else x=1;
        u=f[u];
    }

    int flag=1;
    auto dfs2=[&](auto &self,int a,int fat)->void {
        if(!flag)return;
        for(int i=h[a];i!=-1;i=ne[i]) {
            int b=e[i];
            if(b==fat||vis[b])continue;
            vis[b]=1;
            if(st.find(val[a]/2)==st.end()) {
                val[b]=val[a]/2;
                st.insert(val[a]/2);
            }else if(st.find(val[a]*2+1)==st.end()){
                val[b]=val[a]*2+1;
                st.insert(val[b]);
            }
            else if(st.find(val[a]*2)==st.end()) {
                val[b]=val[a]*2;
                st.insert(val[b]);
            }

            else {
                flag=0;
                return;
            }
            self(self,b,a);
        }
    };

    u=root2;
    while(u!=root1) {
        dfs2(dfs2,u,0);
        u=f[u];
        if(!flag)return false;
    }
    return true;
}

struct DSU {
    vector<int> fa, siz;

    DSU() {
    }

    DSU(int n) {
        init(n);
    }

    void init(int n) {
        fa.resize(n);
        iota(fa.begin(), fa.end(), 0);
        siz.assign(n, 1);
    }

    int find(int x) {
        while (x != fa[x]) {
            x = fa[x] = fa[fa[x]];
        }
        return x;
    }

    bool same(int x, int y) {
        return find(x) == find(y);
    }

    bool merge(int x, int y) {
        x = find(x);
        y = find(y);
        if (x == y) {
            return false;
        }
        siz[x] += siz[y];
        fa[y] = x;
        return true;
    }

    int size(int x) {
        return siz[find(x)];
    }
};
void solve() {
    cin>>n>>m;
    DSU dsu(n+1);
    for(int i=1;i<=n;i++)h[i]=-1;
    idx=0;
    int sign=1;
    for(int i=1;i<=m;i++) {
        int u,v;
        cin>>u>>v;
        d[u]++,d[v]++;
        if(d[u]>3||d[v]>3)sign=0;
        add(u,v),add(v,u);
        if(dsu.same(u,v)) {
            sign=0;
        }
        else dsu.merge(u,v);
    }
    if(dsu.size(1)!=n)sign=0;
    if(!sign) {
        cout<<"NIE"<<"\n";
        return;
    }
    len=0;
    dfs(1,0);
    root1=root;
    memset(f,0,sizeof(f));
    memset(dep,0,sizeof(dep));
    len=0;
    dfs(root,0);
    root2=root;
    dfs3(root2,0);
    //cerr<<"root: "<<root1<<" "<<root2<<"\n";
    //cerr<<"fa: "<<fa[root2]<<"\n";
    LL ans=0;
    auto get_ans=[&]() {
        //cerr<<"val: ";
        for(int i=1;i<=n;i++) {
            if(val[i]>=INF||val[i]<0) {
                //if(n==200000)cout<<"aaa"<<"\n";
                return false;
            }
            ans+=val[i];
            //cerr<<val[i]<<" ";
        }
        return true;
        //cerr<<"\n";
    };
    LL tmp=-1;
    if(work(0,root1,root2,f)&&get_ans()) {
        tmp==-1?tmp=ans:tmp=min(ans,tmp);
    }
    if(work(0,root2,root1,f2)&&get_ans()) {
        tmp==-1?tmp=ans:tmp=min(ans,tmp);
    }
    if(work(1,root1,root2,f)&&get_ans()) {
        tmp==-1?tmp=ans:tmp=min(ans,tmp);
    }
    if(work(1,root2,root1,f2)&&get_ans()) {
        tmp==-1?tmp=ans:tmp=min(ans,tmp);
    }
    if(tmp==-1)cout<<"NIE"<<"\n";
    else cout<<tmp<<"\n";
    
}
/*
4 3
1 2
1 3
1 4

4 6
1 2
2 3
3 4
4 1
1 3
2 4

 */
signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int T=1;
    //cin>>T;
    while(T--)solve();
    return 0;
}

詳細信息

Test #1:

score: 100
Accepted
time: 0ms
memory: 15828kb

input:

4 3
1 2
1 3
1 4

output:

6

result:

ok single line: '6'

Test #2:

score: 0
Accepted
time: 2ms
memory: 11796kb

input:

4 6
1 2
2 3
3 4
4 1
1 3
2 4

output:

NIE

result:

ok single line: 'NIE'

Test #3:

score: 0
Accepted
time: 1ms
memory: 11948kb

input:

10 10
9 3
5 10
1 4
10 8
8 3
7 3
9 6
8 6
7 2
4 5

output:

NIE

result:

ok single line: 'NIE'

Test #4:

score: 0
Accepted
time: 310ms
memory: 32844kb

input:

200000 199999
172774 188052
195063 155577
38023 148303
30605 155047
170238 19344
46835 58255
154268 109062
197059 116041
136424 12058
42062 149807
109545 115380
132322 51106
16706 162612
62234 31319
195735 80435
173898 84051
19876 102910
186924 9136
123094 117097
145054 173049
137364 152731
82662 18...

output:

NIE

result:

ok single line: 'NIE'

Test #5:

score: -100
Wrong Answer
time: 341ms
memory: 32920kb

input:

200000 199999
168192 30733
164413 46673
175210 2329
69389 67102
33991 152553
91061 55265
166724 117726
90148 157176
34831 12213
60756 105488
121891 155192
82202 155666
102083 156661
38968 75200
190004 107321
72436 92732
64314 65004
39210 91106
70455 173568
179742 29844
126232 19552
133509 110602
131...

output:

NIE

result:

wrong answer 1st lines differ - expected: '20980030044349', found: 'NIE'