글 읽기 - 데이터가 이상합니다.

jason9319 5년 전 0

틀린 데이터가 있는것은 아닌데

n,m <10^5 의 문제를 nlogn으로 해결했음에도 불구하고

ios_base::sync_with_stdio(false);

cin.tie(0);

를 겸한 c++ i/o로는 44ms AC

scanf&printf는 tle를 받습니다.

n,m이 10^6도 아니라 10^5인데다가 입출력이 시간초과가 날 정도로 엄청나게 많다고 생각되지는 않는데 너무 큰 차이인것 같습니다 ㅜㅜ..

//아래는 ac를 받은 소스 입니다.

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int n,m,x,y,z,st[100010],ed[100010],tree[100010],c;
vector<vector<int>> vt;
void upd(int x,int val){
    for(int i=x;i<=n;i+=i&-i)
        tree[i]+=val;
}
int query(int x){
    int ret=0;
    for(int i=x;i>0;i-=i&-i)
        ret+=tree[i];
    return ret;
}
int dfs(int here){
    ed[here]=st[here]=++c;
    for(auto next:vt[here])
        ed[here]=max(dfs(next),ed[here]);
    return ed[here];
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin>>n>>m;
    vt.resize(n+1);
    for(int i=1;i<=n;i++){
        cin>>x;
        if(i!=1)vt[x].push_back(i);
    }
    dfs(1);
    for(int i=0;i<m;i++){
        cin>>x>>y;
        if(x==1){
            cin>>z;
            upd(st[y],z);
        }
        else
            cout<<query(ed[y])-query(st[y]-1)<<"\n";
    }
    return 0;
}


//아래는 tle를 받은 소스입니다.

#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
int n,m,x,y,z,st[100010],ed[100010],tree[100010],c;
vector<vector<int>> vt;
void upd(int x,int val){
    for(int i=x;i<=n;i+=i&-i)
        tree[i]+=val;
}
int query(int x){
    int ret=0;
    for(int i=x;i>0;i-=i&-i)
        ret+=tree[i];
    return ret;
}
int dfs(int here){
    ed[here]=st[here]=++c;
    for(auto next:vt[here])
        ed[here]=max(dfs(next),ed[here]);
    return ed[here];
}
int main(){
    scanf("%d%d",&n,&m);
    vt.resize(n+1);
    for(int i=1;i<=n;i++){
        scanf("%d",&x);
        if(i!=1)vt[x].push_back(i);
    }
    dfs(1);
    for(int i=0;i<m;i++){
        scanf("%d%d",&x,&y);
        if(x==1){
            scanf("%d",&z);
            upd(st[y],z);
        }
        else
            printf("%d\n",query(ed[y])-query(st[y]-1));
    }
    return 0;
}