oj.uz

답안 #797143

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
797143 2023-07-29T07:17:22 Z Khizri 열대 식물원 (Tropical Garden) (IOI11_garden) C++17
49 / 100
 104 ms 94196 KB 
#include "garden.h"
#include "gardenlib.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define F first
#define S second
#define INF 1e18
#define all(v) (v).begin(),(v).end()
#define rall(v) (v).rbegin(),(v).rend()
#define pii pair<int,int>
#define pll pair<ll,ll>
#define OK cout<<"Ok"<<endl;
#define MOD (ll)(1e9+7)
const int mxn=2e5+5;
int n,m,fin,k,best[mxn][3],go[mxn][40];
vector<int>vt[mxn];
void count_routes(int N, int M, int P, int R[][2], int Q, int G[])
{
    n=N,m=M,fin=P+1,k=G[0];
    for(int i=0;i<m;i++){
        int u=R[i][0]+1,v=R[i][1]+1;
        if(!best[u][0]){
            best[u][0]=v;
        }
        else if(!best[u][1]){
            best[u][1]=v;
        }
        if(!best[v][0]){
            best[v][0]=u;
        }
        else if(!best[v][1]){
            best[v][1]=u;
        }
    }
    for(int i=1;i<=n;i++){
        if(!best[i][1]){
            best[i][1]=best[i][0];
        }
    }
    for(int u=1;u<=n;u++){
        int x=best[u][0],y=best[u][1];
        if(best[x][0]==u){
            go[u][0]=x+n;
        }
        else{
            go[u][0]=x;
        }
        if(best[y][0]==u){
            go[u+n][0]=y+n;
        }
        else{
            go[u+n][0]=y;
        }
    }
    for(int i=1;i<32;i++){
        for(int u=1;u<=2*n;u++){
            go[u][i]=go[go[u][i-1]][i-1];
        }
    }
    int ans=0;
    for(int u=1;u<=n;u++){
        int node=u;
        for(int i=31;i>=0;i--){
            if(k&(1<<i)){
                node=go[node][i];
            }
        }
        if(node==fin||node==fin+n){
            ans++;
        }
    }
    answer(ans);
}

Subtask #1
49.0 / 49.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 5204 KB Output is correct
2 Correct 3 ms 5272 KB Output is correct
3 Correct 3 ms 5332 KB Output is correct
4 Correct 2 ms 4948 KB Output is correct
5 Correct 2 ms 5008 KB Output is correct
6 Correct 3 ms 5336 KB Output is correct
7 Correct 2 ms 4948 KB Output is correct
8 Correct 3 ms 5340 KB Output is correct
9 Correct 4 ms 5464 KB Output is correct

Subtask #2
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 5204 KB Output is correct
2 Correct 3 ms 5272 KB Output is correct
3 Correct 3 ms 5332 KB Output is correct
4 Correct 2 ms 4948 KB Output is correct
5 Correct 2 ms 5008 KB Output is correct
6 Correct 3 ms 5336 KB Output is correct
7 Correct 2 ms 4948 KB Output is correct
8 Correct 3 ms 5340 KB Output is correct
9 Correct 4 ms 5464 KB Output is correct
10 Correct 2 ms 5080 KB Output is correct
11 Correct 14 ms 12756 KB Output is correct
12 Correct 27 ms 18184 KB Output is correct
13 Correct 104 ms 34404 KB Output is correct
14 Runtime error 82 ms 94196 KB Execution killed with signal 11
15 Halted 0 ms 0 KB -

Subtask #3
0 / 31.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 5204 KB Output is correct
2 Correct 3 ms 5272 KB Output is correct
3 Correct 3 ms 5332 KB Output is correct
4 Correct 2 ms 4948 KB Output is correct
5 Correct 2 ms 5008 KB Output is correct
6 Correct 3 ms 5336 KB Output is correct
7 Correct 2 ms 4948 KB Output is correct
8 Correct 3 ms 5340 KB Output is correct
9 Correct 4 ms 5464 KB Output is correct
10 Correct 2 ms 5080 KB Output is correct
11 Correct 14 ms 12756 KB Output is correct
12 Correct 27 ms 18184 KB Output is correct
13 Correct 104 ms 34404 KB Output is correct
14 Runtime error 82 ms 94196 KB Execution killed with signal 11
15 Halted 0 ms 0 KB -