QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#651277	#7503. Too Many Edges	ucup-team5071^#	RE	0ms	3540kb	C++20	1.8kb	2024-10-18 17:34:20	2024-10-18 17:34:21

Judging History

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

[2024-10-18 17:34:21]
评测

测评结果：RE
用时：0ms
内存：3540kb

查看

[2024-10-18 17:34:20]
提交

answer

#include <bits/stdc++.h>
using namespace std;
const int maxn=5e4+10;
vector<pair<int,int>>ve[maxn];
map<pair<int,int>,int>ma;
int query(int x,int y){
    if(ma.find({x,y})!=ma.end())return ma[{x,y}];
    cout<<"?"<<" "<<x<<" "<<y<<endl;
    int z;cin>>z;
    ma[{x,y}]=z;
    return z;
}
void answer(int x){
    cout<<"! "<<x<<endl;
    exit(0);
}
int gmax(int &x,int y){
    if(y>x){x=y;return 1;}
    return 0;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n,m;cin>>n>>m;
    for(int i=1;i<=m;i++){
        int x,y;cin>>x>>y;
        ve[x].emplace_back(y,i);
    }
    vector<int> ok(n+1);
    bool flag=true;
    while(flag){
        vector<int> in(n+1);
        for(int i=1;i<=n;i++){
            for(auto [to,t]:ve[i])if(ok[t]!=-1){
                in[to]++;
            }
        }    
        queue<int> qu;
        vector<int> dp(n+1);
        for(int i=1;i<=n;i++)if(!in[i])qu.push(i);
        vector<int> pr(n+1),edge(n+1);
        while(!qu.empty()){
            int x=qu.front();qu.pop();
            for(auto [to,t]:ve[x])if(ok[t]!=-1){
                if(gmax(dp[to],dp[x]+1))pr[to]=x,edge[to]=t;
                if((--in[to])==0)qu.push(to);
            }
        }
        int mx=1;
        for(int i=1;i<=n;i++)if(dp[i]>dp[mx])mx=i;
        vector<tuple<int,int,int>> v;
        for(int t=1,now=mx;t<=dp[mx];t++){
            v.emplace_back(pr[now],now,edge[now]);
            now=pr[now];
        }
        reverse(v.begin(),v.end());
        flag=false;
        for(auto [x,y,id]:v){
            if(!query(x,y)){
                flag=true;
                ok[id]=-1;
            }
            else ok[id]=1;
        }
        if(!flag)answer(dp[mx]);
    }
}

/*
5 5
1 2
1 3
2 5
3 4
4 5

*/

源文件, 语言: C++20

詳細信息

Test #1:

score: 100

Accepted

time: 0ms

memory: 3540kb

input:

output:

result:

ok Correct answer

Test #2:

score: -100

Runtime Error

input:

output: