Submission #448223

#	Time	Username	Problem	Language	Result	Execution time	Memory
448223		cpp219	스파이 (JOI13_spy)	C++14	100 / 100	275 ms	45344 KiB

spy

#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")

#include<bits/stdc++.h>
#define ll int
#define ld long double
#define fs first
#define sc second
using namespace std;
typedef pair<ll,ll> LL;
const ll N = 2e3 + 9;
const ll inf = 1e9 + 7;
vector<ll> g1[N],g2[N];
ll n,Q,x,y,JOI,IOI,a[N][N];
ll id_JOI[N],id_IOI[N],cur = 1,par_JOI[N],par_IOI[N];
void DFS_JOI(ll u,ll p){
    id_JOI[u] = cur; cur++; par_JOI[u] = p;
    for (auto i : g1[u]) if (i != p) DFS_JOI(i,u);
}

void DFS_IOI(ll u,ll p){
    id_IOI[u] = cur; cur++; par_IOI[u] = p;
    for (auto i : g2[u]) if (i != p) DFS_IOI(i,u);
}
ll dp[2500][2500];

ll f(ll x,ll y){
    if (x == 0||y == 0) return 0;
    if (dp[x][y] != -1) return dp[x][y];
    ll p = par_JOI[x],q = par_IOI[y];
    ll cx = id_JOI[x],cy = id_IOI[y];
    ll ans = f(p,y) + f(x,q) - f(p,q) + a[cx][cy];
    return dp[x][y] = ans;
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    #define task "tst"
    if (fopen(task".INP","r")){
        freopen(task".INP","r",stdin);
        //freopen(task".OUT","w",stdout);
    }
    cin>>n>>Q;
    for (ll i = 1;i <= n;i++){
        cin>>x>>y;
        if (!x) JOI = i;
        else g1[x].push_back(i);
        if (!y) IOI = i;
        else g2[y].push_back(i);
    }
    DFS_JOI(JOI,0); cur = 1; DFS_IOI(IOI,0);  memset(dp,-1,sizeof(dp));
    while(Q--){
        cin>>x>>y;
        ll p = id_JOI[x],q = id_IOI[y]; a[p][q]++;
    }
    //for (ll i = 1;i <= n;i++) cout<<id_JOI[i]<<" "<<id_IOI[i]<<"\n"; return 0;
    for (ll i = 1;i <= n;i++) cout<<f(i,i)<<"\n";
}

Compilation message (stderr)

spy.cpp:2: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    2 | #pragma GCC optimization ("O3")
      | 
spy.cpp:3: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    3 | #pragma GCC optimization ("unroll-loops")
      | 
spy.cpp: In function 'int main()':
spy.cpp:42:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   42 |         freopen(task".INP","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 20 / 20
• Subtask 3: 70 / 70