oj.uz

Submission #16315

# Submission time Handle Problem Language Result Execution time Memory
16315 2015-08-20T11:32:40 Z khsoo01 Tropical Garden (IOI11_garden) C++
49 / 100
 5000 ms 12304 KB 
#include<bits/stdc++.h>
#include "garden.h"
#include "gardenlib.h"
#define INF 0x7fffffff
using namespace std;
vector<int>cg[150005],cn[150005];
int n,m,p,ed[150005][2],cur,flag,vis[150005],cnt;
bool state;

struct destination {
    int dist[150005],cyc_len;
    bool in_cyc;
}d[2];

void find_cyc(int idx) {
    if(vis[idx]==1) {
        if(!d[state].in_cyc && idx!=cn[p][state]) return;
        d[state].in_cyc=true;
        d[state].cyc_len++;
    }
    if(vis[idx]==2) return;
    vis[idx]++;
    find_cyc(cn[ed[idx][1]][(cg[ed[idx][1]][0]==ed[idx][0] && cg[ed[idx][1]].size()>1)?1:0]);
    vis[idx]=0;
}

void find_dist(int idx) {
    if(idx==cn[p][state]) {
        d[state].dist[cur]=0;
        return;
    }
    if(vis[idx]) {
        d[state].dist[cur]=-INF;
        return;
    }
    vis[idx]++;
    find_dist(cn[ed[idx][1]][(cg[ed[idx][1]][0]==ed[idx][0] && cg[ed[idx][1]].size()>1)?1:0]);
    vis[idx]=0;
    d[state].dist[cur]++;
}

void count_routes(int N, int M, int P, int R[][2], int Q, int G[])
{
    int i,j,k; n=N; m=M; p=P;
    for(i=0;i<m;i++) {
        ed[i][0]=R[i][0];
        ed[i][1]=R[i][1];
        ed[i+m][0]=R[i][1];
        ed[i+m][1]=R[i][0];
        cg[ed[i][0]].push_back(ed[i][1]);
        cn[ed[i][0]].push_back(i);
        cg[ed[i][1]].push_back(ed[i][0]);
        cn[ed[i][1]].push_back(i+m);
    }
    d[0].cyc_len=0; d[0].in_cyc=false;
    d[1].cyc_len=0; d[1].in_cyc=false;
    state=0;
    find_cyc(cn[p][0]);
    state=1;
    find_cyc(cn[p][1]);
    for(cur=0;cur<n;cur++) {
        state=0;
        find_dist(cn[cur][0]);
        state=1;
        find_dist(cn[cur][0]);
    }
    for(i=0;i<Q;i++) {
        cnt=0;
        for(j=0;j<n;j++) {
            flag=0;
            for(k=0;k<2;k++) {
                if(d[k].dist[j]<0) continue;
                if(d[k].dist[j]==G[i])flag=1;
                if(d[k].dist[j]<G[i] && d[k].in_cyc && (G[i]-d[k].dist[j])%d[k].cyc_len==0)flag=1;
            }
            if(flag)cnt++;
        }
        answer(cnt);
    }
}

Subtask #1
49.0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 7516 KB Output is correct
2 Correct 11 ms 7484 KB Output is correct
3 Correct 12 ms 7544 KB Output is correct
4 Correct 9 ms 7416 KB Output is correct
5 Correct 9 ms 7416 KB Output is correct
6 Correct 25 ms 7544 KB Output is correct
7 Correct 8 ms 7416 KB Output is correct
8 Correct 10 ms 7544 KB Output is correct
9 Correct 12 ms 8056 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 7516 KB Output is correct
2 Correct 11 ms 7484 KB Output is correct
3 Correct 12 ms 7544 KB Output is correct
4 Correct 9 ms 7416 KB Output is correct
5 Correct 9 ms 7416 KB Output is correct
6 Correct 25 ms 7544 KB Output is correct
7 Correct 8 ms 7416 KB Output is correct
8 Correct 10 ms 7544 KB Output is correct
9 Correct 12 ms 8056 KB Output is correct
10 Correct 8 ms 7416 KB Output is correct
11 Correct 2958 ms 9996 KB Output is correct
12 Execution timed out 5063 ms 12304 KB Time limit exceeded
13 Halted 0 ms 0 KB -

Subtask #3
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 7516 KB Output is correct
2 Correct 11 ms 7484 KB Output is correct
3 Correct 12 ms 7544 KB Output is correct
4 Correct 9 ms 7416 KB Output is correct
5 Correct 9 ms 7416 KB Output is correct
6 Correct 25 ms 7544 KB Output is correct
7 Correct 8 ms 7416 KB Output is correct
8 Correct 10 ms 7544 KB Output is correct
9 Correct 12 ms 8056 KB Output is correct
10 Correct 8 ms 7416 KB Output is correct
11 Correct 2958 ms 9996 KB Output is correct
12 Execution timed out 5063 ms 12304 KB Time limit exceeded
13 Halted 0 ms 0 KB -