oj.uz

답안 #121327

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
121327 2019-06-26T10:31:10 Z baqargam 열대 식물원 (Tropical Garden) (IOI11_garden) C++14
0 / 100
 16 ms 14624 KB 
#include<bits/stdc++.h>
#include "garden.h"
#include "gardenlib.h"

using namespace std;

int d[300005],a,k,n,m,q,p,c[300005],d2[300005],v1[300005],sz,sz1,sz2,st,fx[300005],ch,res[2005];
vector<pair<int,int> >v[300005];
vector<int>rv[300005];
set<int>s;

void cch(int x,int dis,int st){
    for(int i=0;i<rv[x].size();i++){
        if(rv[x][i]==st) {sz=dis+1;return;}
        cch(rv[x][i],dis+1,st);
    }
}

void dfs(int x,int dis,int st){
    //cout<<st<<" "<<x<<" "<<dis<<" "<<k<<" "<<sz<<endl;
    if(x%2==0 && (k%sz)==(dis%sz))
    {
        s.insert(x/2);
    }
    for(int i=0;i<rv[x].size();i++){
        if(rv[x][i]==st) continue;
        dfs(rv[x][i],dis+1,st);
    }
}

void count_routes(int N, int M, int P, int R[][2], int Q, int G[])
{
    int n=N,m=M,p=P;
    for(int i=0;i<m;i++){///grafi1
        int a=R[i][0];
        int b=R[i][1];
        v[a].push_back({i,b});
        v[b].push_back({i,a});
    }
    for(int i=0;i<n;i++){
        sort(v[i].begin(),v[i].end());
    }
    for(int i=0;i<n;i++){///grafi2
        if(v[i].size()==1)
        {
            int to=v[i][0].second;
            int val=v[i][0].first;
            if(v[to][0].first==val)
                v1[2*i+1]=2*to+1;
            else
                v1[2*i+1]=2*to;

            if(v[to][0].first==val)
                v1[2*i]=2*to+1;
            else
                v1[2*i]=2*to;
        }
        else
        {
            int to=v[i][0].second;
            int val=v[i][0].first;
//            cout<<i<<" "<<to<<" "<<val<<" "<<v[to][0].first<<endl;
            if(v[to][0].first==val)
                v1[2*i]=2*to+1;
            else
                v1[2*i]=2*to;

            to=v[i][1].second;
            val=v[i][1].first;
//            cout<<i<<" "<<to<<" "<<val<<" "<<v[to][0].first<<endl;
            if(v[to][0].first==val)
                v1[2*i+1]=2*to+1;
            else
                v1[2*i+1]=2*to;

        }
    }

    for(int i=0;i<2*n;i++){
        rv[v1[i]].push_back(i);
    }


    sz=100000000;cch(2*p,0,2*p);sz1=sz;
    sz=100000000;cch(2*p+1,0,2*p+1);sz2=sz;

    for(int i=0; i<Q; i++)
    {
        k=G[i];
        s.clear();
        sz=sz1;dfs(2*p,0,2*p);
        sz=sz2;dfs(2*p+1,0,2*p+1);
        answer(s.size());
    }
}

Compilation message

garden.cpp: In function 'void cch(int, int, int)':
garden.cpp:13:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<rv[x].size();i++){
                 ~^~~~~~~~~~~~~
garden.cpp: In function 'void dfs(int, int, int)':
garden.cpp:25:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<rv[x].size();i++){
                 ~^~~~~~~~~~~~~

Subtask #1
0 / 49.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 16 ms 14624 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 16 ms 14624 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 31.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 16 ms 14624 KB Output isn't correct
2 Halted 0 ms 0 KB -