제출 #148126

#제출 시각아이디문제언어결과실행 시간메모리
148126WhipppedCream열대 식물원 (Tropical Garden) (IOI11_garden)C++17
컴파일 에러
0 ms0 KiB
#include <bits/stdc++.h> #define ii pair<int, int> #define X first #define Y second #define pb push_back #define vi vector<int> #define vii vector< pair<int, int> > typedef long long ll; using namespace std; vector< ii > adj[150005]; bool cmp(ii A, ii B) { return A.second < B.second; } ii To[150005][2]; int deg[150005][2]; int Best[150005]; int Res[150005]; int cyc_id[150005][2]; int cyc_pos[150005][2]; vii cyc[150005]; int visit[150005][2]; int Steps[150005][2]; int realcycle[150005][2]; ii plaicycle[150005][2]; int cyc_cnt = 1; int joe[150005][2]; int p; ii find_paths(int u, int stat) { //printf("called %d %d\n", u, stat); if(realcycle[u][stat]) { return ii(-1, -1); } if(visit[u][stat] == 1) { return ii(u, stat); } if(joe[u][stat] == 1) { return ii(-1, -1); } joe[u][stat] = 1; visit[u][stat] = 1; ii tmp = To[u][stat]; ii res = find_paths(tmp.X, tmp.Y); visit[u][stat] = 0; if(res.X != -1) { cyc_id[u][stat] = cyc_cnt; cyc_pos[u][stat] = cyc[cyc_cnt].size(); //printf("%d %d is in cycle\n", u, stat); cyc[cyc_cnt].pb(ii(u, stat)); realcycle[u][stat] = 1; if(res.X == u && res.Y == stat) { cyc_cnt++; return ii(-1, -1); } return res; } Steps[u][stat] = Steps[To[u][stat].X][To[u][stat].Y]+1; cyc_id[u][stat] = cyc_id[To[u][stat].X][To[u][stat].Y]; if(realcycle[To[u][stat].X][To[u][stat].Y]) plaicycle[u][stat] = To[u][stat]; else plaicycle[u][stat] = plaicycle[To[u][stat].X][To[u][stat].Y]; return ii(-1, -1); } ii dp[150005][2][20]; int findEnd(int start, int stat, int steps) { //printf("called %d %d %d\n", start, stat, steps); int x = cyc_id[start][stat]; int y = cyc_id[p][0]; int z = cyc_id[p][1]; if(x != y && x != z) return -1; if(realcycle[start][stat]) { int id = cyc_id[start][stat]; int n = cyc[id].size(); int pos = n-1-cyc_pos[start][stat]; //printf("pos is %d\n", pos); pos += steps; pos %= n; return cyc[id][pos].X; } else { //printf("not in cycle\n"); int x = Steps[start][stat]; if(x< steps) { return findEnd(plaicycle[start][stat].X, plaicycle[start][stat].Y, steps-x); } else { int cur_a = start; int cur_b = stat; for(int i = 17; i>= 0; i--) { if((1<<i) <= steps) { steps -= (1<<i); int tmp_a = dp[cur_a][cur_b][i].X; int tmp_b = dp[cur_a][cur_b][i].Y; cur_a = tmp_a; cur_b = tmp_b; } } return cur_a; } } } int main() { memset(Res, -1, sizeof Res); int n, m; scanf("%d %d %d", &n, &m, &p); for(int i = 0; i< m; i++) { int u, v; scanf("%d %d", &u, &v); adj[u].pb(ii(v, i)); adj[v].pb(ii(u, i)); } for(int i = 0; i< n; i++) { sort(adj[i].begin(), adj[i].end(), cmp); while((int) adj[i].size() > 2) adj[i].pop_back(); Best[i] = adj[i][0].X; if((int) adj[i].size() == 2) Res[i] = adj[i][1].X; //printf("%d: %d %d\n", i, Best[i], Res[i]); } for(int i = 0; i< n; i++) { int tmp = Best[i]; int aug; if(Best[tmp] == i) aug = 1; else aug = 0; To[i][0]= ii(tmp, aug); //if(i == 0) printf("dfjsklfjdsjkldjsfkdjslkfjdlsj %d %d\n", tmp, aug); deg[tmp][aug]++; int k = Res[i]; if(k == -1) k = Best[i]; if(Best[k] == i) aug = 1; else aug = 0; if(k == -1) k = Best[i]; To[i][1] = ii(k, aug); deg[k][aug]++; //if((tmp == 0 || k == 0) && aug == 0) printf("sfdksfjdasfjklsfjkl %d\n", i); } //printf("shittttttttt %d\n", deg[0][0]); for(int i = 0; i< n; i++) { for(int j = 0; j< 2; j++) { if(joe[i][j] == 0) { //printf("dfs at %d %d\n", i, j); find_paths(i, j); } } } for(int i = 1; i< cyc_cnt; i++) { reverse(cyc[i].begin(), cyc[i].end()); } /*printf("---paths\n"); printf("paths count = %d\n", paths_cnt); for(int i = 1; i< paths_cnt; i++) { printf("[[[[[[[[[[[[[[[[[[[[[%d]]]]]]]]]]]]]]]]]]]]", i); for(int j = 0; j< (int) paths[i].size(); j++) { printf("(%d, %d)", paths[i][j].X, paths[i][j].Y); } printf("-------------------------\n"); }*/ /*printf("---cycles\n"); for(int i = 1; i< cyc_cnt; i++) { for(int j = 0; j< (int) cyc[i].size(); j++) { printf("(%d, %d)", cyc[i][j].X, cyc[i][j].Y); } printf("-------------------------------------------\n"); } printf("Plaicycle\n"); */ /*for(int i = 0; i< n; i++) { for(int j = 0; j< 2; j++) { printf("%d %d: %d %d (%d)\n", i, j, plaicycle[i][j].X, plaicycle[i][j].Y, Steps[i][j]); } }*/ for(int i = 0; i< n; i++) { for(int j = 0; j< 2; j++) { if(realcycle[i][j]) dp[i][j][0] = ii(i, j); else dp[i][j][0] = To[i][j]; } } for(int k = 1; k< 18; k++) { for(int i= 0; i< n; i++) { for(int j= 0; j< 2; j++) { int a = dp[i][j][k-1].X; int b = dp[i][j][k-1].Y; dp[i][j][k] = dp[a][b][k-1]; } } } int tt; scanf("%d", &tt); while(tt--) { int k; scanf("%d", &k); int ans = 0; for(int i = 0; i< n; i++) { int res = findEnd(i, 0, k); //printf("%d %d ends at %d\n", i, 0, res); if(res == p) { ans++; } } printf("%d ", ans); } return 0; }

컴파일 시 표준 에러 (stderr) 메시지

garden.cpp: In function 'int main()':
garden.cpp:118:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d %d", &n, &m, &p);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
garden.cpp:122:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d", &u, &v);
         ~~~~~^~~~~~~~~~~~~~~~~
garden.cpp:218:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &tt);
     ~~~~~^~~~~~~~~~~
garden.cpp:222:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &k);
         ~~~~~^~~~~~~~~~
/tmp/cceyh695.o: In function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'
/tmp/cc7bBorr.o:garden.cpp:(.text.startup+0x0): first defined here
/tmp/cceyh695.o: In function `main':
grader.cpp:(.text.startup+0x38): undefined reference to `count_routes(int, int, int, int (*) [2], int, int*)'
collect2: error: ld returned 1 exit status