TLE in Foe Pairs (Educational Codeforces Round 10)

Question

关于为 Foe Pairs 问题实现复杂度为 O(N+M) 的代码 http://codeforces.com/contest/652/problem/C，我在测试用例 12 中得到 TLE。

约束：(1 ≤⟩N,⟩M ≤ 3·105)

我没明白，为什么这个约束 O(N+M) 得到 TLE。

这里是代码

#include<iostream>
#include<vector>

using namespace std;
int main()
{
    int n,m;
    cin>>n>>m;
    std::vector<int> v(n+1);
    for (int i = 0; i < n; ++i)
    {
        int x;
        cin>>x;
        v[x] = i;
    }
    std::vector<int> dp(n,0);
    for (int i = 0; i < m; ++i)
    {
        int a,b;
        cin>>a>>b;
        if(v[a]>v[b])
            swap(a,b);
        dp[v[b]] = max(dp[v[b]], v[a]+1);
    }
    for (int i = 1; i < n; ++i)
    {
        dp[i] = max(dp[i], dp[i-1]);
    }
    long long s = 0;

    for (int i = 0; i < n; ++i)
    {
        s+=(i+1-dp[i]);
    }
    cout<<s;
}

我有什么遗漏吗？

Answer 1

我把所有的cin改成了scanf，它通过了所有的测试用例：http://codeforces.com/contest/652/submission/17014495

#include<cstdio>
#include<iostream>
#include<vector>

using namespace std;
int main()
{
    int n,m;
    scanf("%d%d", &n, &m);
    //cin>>n>>m;
    std::vector<int> v(n+1);
    for (int i = 0; i < n; ++i)
    {
        int x;
        //cin>>x;
        scanf("%d", &x);
        v[x] = i;
    }
    std::vector<int> dp(n,0);
    for (int i = 0; i < m; ++i)
    {
        int a,b;
        //cin>>a>>b;
        scanf("%d%d", &a, &b);
        if(v[a]>v[b])
            swap(a,b);
        dp[v[b]] = max(dp[v[b]], v[a]+1);
    }
    for (int i = 1; i < n; ++i)
    {
        dp[i] = max(dp[i], dp[i-1]);
    }
    long long s = 0;

    for (int i = 0; i < n; ++i)
    {
        s+=(i+1-dp[i]);
    }
    cout<<s;
    return 0;
}

当输入量很大时，您应该始终尝试使用 scanf，因为它速度更快。

您可以在此处阅读有关 scanf 更快的更多信息：Using scanf() in C++ programs is faster than using cin?

TLE in Foe Pairs (Educational Codeforces Round 10)

TLE in Foe Pairs (Educational Codeforces Round 10)

optimization

runtime

time-complexity

dynamic-programming