oj.uz

답안 #1092139

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1092139 2024-09-23T09:44:59 Z Aviansh 열대 식물원 (Tropical Garden) (IOI11_garden) C++17
0 / 100
 1 ms 604 KB 
#include <bits/stdc++.h>
#include "garden.h"
#include "gardenlib.h"

using namespace std;

void dfs(int st, int dep, vector<int>(&g)[], int f[], bool vis[], int t, int p, int n){
    vis[st]=1;
    //cout << "visiting: " << st << endl;
    f[st]=dep;
    for(int i : g[st]){
        if(i==t){
            f[t]=dep+1;
        }
        if(vis[i])
            continue;
        if(i==st+n||i==st-n){
            dfs(i,dep,g,f,vis,t, st, n);
            continue;
        }
        dfs(i,dep+1,g,f,vis,t, st, n);
    }
}

void count_routes(int n, int m, int t, int edges[][2], int q, int G[])
{
    vector<int>g[2*n];
    int cn[n];
    fill(cn,cn+n,0);
    for(int i = 0;i<m;i++){
        int u1=edges[i][0];
        int v1=edges[i][1];
        //cout << u1 << " " << v1 << endl;
        if(cn[u1]>cn[v1]){
            swap(u1,v1);
        }
        int u2 = u1+n;
        int v2 = v1+n;
        if(cn[u1]==0&&cn[v1]==0){
//            cout << "adding1: " << u1 << " " << v2 << endl;
  //          cout << "adding2: " << v1 << " " << u2 << endl;
            g[v2].push_back(u1);
            g[u2].push_back(v1);
        }
        else if(cn[u1]==0&&cn[v1]==1){
    //        cout << "adding3: " << u1 << " " << v1 << endl;
      //      cout << "adding4: " << v2 << " " << u2 << endl;
            g[v1].push_back(u1);
            g[u2].push_back(v2);
        }
        else if(cn[u1]==0&&cn[v1]>1){
        //    cout << "adding5: " << u1 << " " << v1 << endl;
            g[v1].push_back(u1);
        }
        else if(cn[u1]==1&&cn[v1]==1){
            //cout << "adding6: " << u2 << " " << v1 << endl;
            //cout << "adding7: " << v2 << " " << u1 << endl;
            g[v1].push_back(u2);
            g[u1].push_back(v2);
        }
        else if(cn[u1]==1&&cn[v1]>1){
            //cout << "adding8: " << u2 << " " << v1 << endl;;
            g[v1].push_back(u2);
        }
        cn[u1]++;
        cn[v1]++;
    }
    for(int i = 0;i<n;i++){
        if(cn[i]==1){
            g[i].push_back(i+n);
            g[i+n].push_back(i);
        }
    }
    int f1[2*n];
    fill(f1,f1+2*n,-1);
    bool vis[2*n];
    fill(vis,vis+2*n,0);
    //cout << "first: \n";
    dfs(t,0,g,f1,vis,t,-1, n);
    int f2[2*n];
    fill(f2,f2+2*n,-1);
    fill(vis,vis+2*n,0);
   // cout << "second: \n";
    dfs(t+n,0,g,f2,vis,t+n,-1, n);
    for(int i = 0;i<q;i++){
        int ans = 0;
//    cout << "here" << endl;
  //      cout << "going in" << endl;
        for(int j = 0;j<n;j++){
    //        cout << "inside loop now2" << endl;
            //cout << i << " " << j << " " << t << " " << n << " " << f1[t] << " " << f1[j] << " " << f2[j] << " " << f2[t+n] <<endl;
            if(f1[j]==G[i]||(f1[t]!=0&&f1[j]!=-1&&f1[j]<=G[i]&&f1[j]%f1[t]==G[i]%f1[t])){
                ans++;
        //        cout << "added 1" << endl;
            }
          //  cout << "outside first if" << endl;
            else if(f2[j]==G[i]||(f2[t+n]!=0&&f2[j]!=-1&&f2[j]<=G[i]&&f2[j]%f2[t+n]==G[i]%f2[t+n])){
                ans++;
            //    cout << "added 1 next" << endl;
            }
        }
        //cout << "answering...";
        answer(ans);
    }
}

Subtask #1
0 / 49.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 600 KB Output is correct
2 Correct 1 ms 604 KB Output is correct
3 Correct 0 ms 604 KB Output is correct
4 Incorrect 0 ms 344 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 600 KB Output is correct
2 Correct 1 ms 604 KB Output is correct
3 Correct 0 ms 604 KB Output is correct
4 Incorrect 0 ms 344 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 31.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 600 KB Output is correct
2 Correct 1 ms 604 KB Output is correct
3 Correct 0 ms 604 KB Output is correct
4 Incorrect 0 ms 344 KB Output isn't correct
5 Halted 0 ms 0 KB -