oj.uz

Submission #448223

# Submission time Handle Problem Language Result Execution time Memory
448223 2021-07-29T10:36:00 Z cpp219 스파이 (JOI13_spy) C++14
100 / 100
 275 ms 45344 KB 
#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

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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 25420 KB Output is correct
2 Correct 12 ms 24908 KB Output is correct
3 Correct 11 ms 25164 KB Output is correct
4 Correct 12 ms 25032 KB Output is correct
5 Correct 11 ms 25292 KB Output is correct
6 Correct 12 ms 24936 KB Output is correct
7 Correct 12 ms 25404 KB Output is correct
8 Correct 12 ms 25408 KB Output is correct
9 Correct 12 ms 24852 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 114 ms 31052 KB Output is correct
2 Correct 116 ms 25340 KB Output is correct
3 Correct 16 ms 28236 KB Output is correct
4 Correct 15 ms 27232 KB Output is correct
5 Correct 25 ms 30696 KB Output is correct
6 Correct 23 ms 25212 KB Output is correct
7 Correct 120 ms 31340 KB Output is correct
8 Correct 33 ms 31392 KB Output is correct

Subtask #3
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 226 ms 45252 KB Output is correct
2 Correct 219 ms 29592 KB Output is correct
3 Correct 120 ms 41232 KB Output is correct
4 Correct 118 ms 45344 KB Output is correct
5 Correct 136 ms 42608 KB Output is correct
6 Correct 108 ms 29664 KB Output is correct
7 Correct 275 ms 45216 KB Output is correct
8 Correct 178 ms 45152 KB Output is correct