Submission #126617

#TimeUsernameProblemLanguageResultExecution timeMemory
126617khulegubFlood (IOI07_flood)C++14
0 / 100
2 ms376 KiB
#include <bits/stdc++.h> #define mp make_pair #define pb push_back #define xx first #define yy second using namespace std; typedef pair<int, int> pii; vector<vector<int> > to; vector<pii> p; int n; int w; int uld; bool path[100010]; bool vis[100010]; int cmpx (int a, int b){ return p[b].xx - p[a].xx; } int cmpy (int a, int b){ return p[b].yy - p[a].yy; } void mark (int u){ vis[u] = 1; for (int i = 0; i < 4; i++){ if(to[u][i] != 0 && !vis[to[u][i]] ){ mark (to[u][i]); } } } int dfs (int u, int pre, int dir){ if (path[u]) return -1; // ustga >:( if(dir == -1){ for (int i = 0; i < 4; i++){ if(to[u][i] != 0){ int tmp = dfs(to[u][i], u, i); if(tmp == -1){ uld--; to[u][i] = 0; to[ to[u][i] ][ (i + 2) % 4 ] = 0; return -1; } } } } int arr[4]; arr[0] = (dir + 1) % 4; arr[1] = dir; arr[2] = (dir + 3) % 4; path[u] = 1; for (int i = 0; i < 3; i++){ if (to[u][arr[i]] != 0){ int tmp = dfs(to[u][arr[i]], u, arr[i]); if(tmp == -1){ uld--; to[u][arr[i]] = 0; to[ to[u][arr[i]] ][ (arr[i] + 2) % 4 ] = 0; return -1; // HUBCoworking } } } path[u] = 0; return 1; } // bool int main() { freopen("in.txt", "r", stdin); cin >> n; to.resize(n + 1, vector<int>(4) ); p.resize(n + 1); vector<pii> wll; for (int i = 1, tx, ty; i <= n; i++){ cin >> tx >> ty; p[i] = mp(tx, ty); } cin >> w; uld = w; wll.resize(w + 1); // cout << to[1].size(); for (int i = 1, a, b; i <= w; i++){ cin >> a >> b; int dx = p[b].xx - p[a].xx, dy = p[b].yy - p[a].yy; if(dy == 0){ if(dx > 0){ // b ni a giin baruun tald to[a][1] = b; wll[i] = mp(a,1); to[b][3] = a; } else{ to[a][3] = b; wll[i] = mp(a,3); to[b][1] = a; } } else if(dx == 0){ if(dy > 0){ // b ni a giin deed tald to[a][0] = b; wll[i] = mp(a,0); to[b][2] = a; } else{ to[a][2] = b; wll[i] = mp(a,2); to[b][0] = a; } } } // cout << to[1][]; for (int i = 1; i <= n; i++){ // cout << to[i][] << ' '; if(!vis[i]){ dfs(i, i, -1); mark(i); } } cout << uld << '\n'; for(int i = 1; i <= w; i++){ if (to[wll[i].xx][wll[i].yy] != 0 ) cout << i << '\n'; } return 0; }

Compilation message (stderr)

flood.cpp: In function 'int main()':
flood.cpp:68:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
  freopen("in.txt", "r", stdin);
  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...